WO2009014465A2

WO2009014465A2 - System and method for multilingual translation of communicative speech

Info

Publication number: WO2009014465A2
Application number: PCT/RS2008/000025
Authority: WO
Inventors: Slobodan Jovicic; Zoran Saric
Original assignee: Slobodan Jovicic; Zoran Saric
Priority date: 2007-07-25
Filing date: 2008-07-16
Publication date: 2009-01-29
Also published as: RS50004B; RS20070316A; WO2009014465A3

Abstract

The invention relates to the system and method for translation of communicative speech using multilingual resources as universal base for multilingual translation. Specific aspect of the invention is the generalized interaction of languages through Interlingua Domain which contains formal descriptions of both speech and language of the source speaker in the form of concepts which are accessible for the synthesis in other languages. The system consists of Interlingua Domain (ID) which contains Interlingua Reservoir of Concepts (IRC) and Interlingua Bank of Bilingual Dictionaries (IBBD). Each language in the translation system has the module with two-way processing of speech and language: analytic towards Interlingua Domain where the sentence in the source language is processed and synthetic from Interlingua Domain where the sentence is generated in the target language. Analytic and synthetic procedures are based on grammatical rules with specific solutions in extraction and synthesis of features, meanings and concepts of two languages in interaction.

Description

SYSTEM AND METHOD FOR MULTILINGUAL TRANSLATION OF COMMUNICATIVE SPEECH

Technical Field

This invention belongs to the area of natural language processing, more precisely to the systems for machine translation of speech from one language to another by the application of interlingua resources as a universal basis for multilingual translation.

Background Art

Machine translation of speech from one language to another implies complex processes which must be carried out between two speakers of different languages by means of a computer. These processes unfold on a number of levels which in the most basic form can be represented as a serial connection of relatively independent modules: Automatic

Speech Recognition - ASR, Machine Translation - MT, and speech synthesis as Text-to-

Speech - TTS. Module ASR performs speech recognition in source language, i.e. conversion of a speech signal into text. Module MT performs machine translation of a text in source language into a text in target language. Finally, module TTS performs synthesis of speech in target language from the text obtained in target language.

This ordinary form of a system for translation from language to language comes across numerous technical problems. These problems are due to extremely complex nature of speech and language. Firstly, speech signal is exceptionally unstable and is subject to many variations (different speakers, speakers' different psycho-emotional states, different influences of ambient noise, variations of speech-language expression, etc.), which eventually do not influence the language information transmitted by speech signal, but which require ASR module to be extremely robust in the process of analysis of a speech signal, identifying phonetic elements and recognition of language content in the speech signal. Contemporary ASR solutions are still far from perfect solutions and accurateness of recognition of speech depends on the speaker, ambient conditions of the recording of speaker and vocabulary extent.

Secondly, MT module is still far from definite solution as regards translation accurateness. Basic problems appear in variations of language expression and vocabulary extent. Furthermore, the question which of the existing models of machine translation offers certain perspective of acceptable solution has not yet been solved. Generally, MT models can be classified into four categories:

- "Rule-based transfer" models. Basic components of these models are: analysis of the source language, transfer of source language structure into target language structure and synthesis of target language. Analysis of a language implies complete grammar analysis of source language. Transfer component between the two grammars

(source and target language) contains bilingual rules of transformation of grammar representation of one language into the other (comparative grammar). Problems of comparative grammar are structural differences of the sentences of two languages, differences in morphological richness of words, as well as lexical problem of polysemantic words, etc. Lexical problem of polysemantic words is the one that does not allow reversible transfer process.

- "Interlingua " models. These models are based on the idea that there is a kind of an interlingua. In that case, for n languages we need n translators into interlingua and n translators from interlingua into target languages; 2n translators in total, hi the case of the solution of given example by rule-based transfer model, where each pair of languages requires its translators in both direction, total number of translators would be n(n - Y). On the other hand, in interlingua approach it is sufficient to have translators from/into interlingua for one language, thus providing communication with any other language, because all languages communicate via the same interlingua. Interlingua is not a natural language, but artificial interlingual interpretation.

- Statistical models. These models consist of two parts: linguistic model and translation model. Linguistic model determines probability of a sentence S in source language P(S) and similarly, probability of a sentence T in target language P(T). Translation model determines conditional probability P(T|S). Product P(S)P(T|S) gives probability of a pair of S and T sentences, P(S₅T). Two tasks need to be solved.

Probability P(S) can be broke down into the product of conditional probabilities:

P(S₁) x P(S₂Is₁) x P(s3|s_l5S2) x ..., where si are words in a sentence S. Probability P(S₂Is₁) expresses probability that word S₂ will happen if word S₁ happened.

Practically, one or two previous words are included when determining conditional probabilities (so-called bigrams and trigrams). The second task is to determine maximal probability P(S₅T). Obviously, these models do not use linguistic knowledge, but extremely comprehensive language base for determination of described probabilities.

- „ Example-based" models. The basic idea of such a model is to form of a comprehensive bilingual corpus of pairs of sentences and/or phrases, and then, by methods of closest similarity, to determine an example (sentence and/or phrase) most similar to the source language and/or phrase. For this purpose, it is most suitable to use previous examples of translation and thus cumulatively increase bilingual corpus.

The advantage of such models is extreme simplicity, independence from linguistic properties of a language in translation and fast development of the system for a new pair of languages. The disadvantage is necessity of comprehensive bilingual corpus and the time of searching through this corpus. Each of these models, or their derivatives, or their combinations have serious disadvantages and limitations and so far, none of them has shown primacy.

Thirdly, from the aspect of correctness of text-to-speech conversion, TTS module is completely solved, but there are still significant problems as regards quality of synthesized speech, primarily in respect of its naturalness. Machine translations of text and speech are very different, which comes from the nature of both. Text is completely stable and grammatically correct language modality. On the other hand, speech very often has unstable, irregular and unlikely structure, which significantly influences the profile of MT system. Besides that, speech proceeds in continuity and there is no time for correction of either recognized, or translated text.

From the aspect of MT technology speech is characterized by: frequent discontinuities and incomplete utterances which, in the context, bear the meaning or express speaker's intention by successive repetition of the same word („... I said that, that..., that I'll come ..."), partially pronounced words („ ... I met him on Sat... hmm, no, on Sunday. "), the use of non-language sounds (,,uh, hmm, aaah"), there is no punctuation in speech, which in the text clearly marks sentences, parts of sentences, as well as function of sentences (declarative, interrogative, exclamatory), etc., which makes it difficult for translation.

These properties of speech in conversation require from the translation system specific linguistic pre-processing of source speech - Natural Language Understanding, NLU, which, on the other hand, in target language requires forming of a module for Natural Language Generation, NLG. Therefore, initial serial connection of three modules (ASR, MT₅ TTS) is now expanded to five modules (ASR, NLU, MT, NLG, TTS).

However, problem has not yet been solved due to individual imperfections of certain modules, which can only degrade final translation results in the serial structure. Contemporary solutions tend towards integration of certain modules, such as ASR and NLU, and use of mutual resources, which increases accuracy of their mutual function. Speech interpersonal communication has gained primacy in contemporary global business communications. However, language barriers present a real drawback in the development of these communications. This contrast has caused very intensive approach to solving the questions of machine (computer) translation from one language to another language, not only on the level of text, but also on the level of speech, which is the most natural and fastest form of understanding between people (R. A. Cole at al.; Survey of the state of the art in human language technology; Oregon Graduate Institute, 1995.). Exceptional variability of speech expression (some of the characteristics are mentioned in the previous chapter) has hindered the very problem of machine translation so much that there has not yet been any satisfactory solutions, nor they can be expected in near future. Such state of facts has generated the whole range of solutions which partially solve certain aspects of translation (Arnold, D., at al. (1994). Machine translation: an introductory guide. NCC Blackwell Ltd.; Wahlster, W., (ed.) (2000). Verbmobil: foundations of speech- to-speech translation. Springer-Verlag, Berlin).

Particular problem in the realization of a system for machine translation from speech to speech is the volume of dictionary and indirectly the question of independence of ASR modules from the speaker. Namely, there are systems for speech recognition with big dictionaries with over 100.000 words (such as e.g. DRAGON system), but they depend on the speaker and require special training prior to usage. This problem will soon be solved by contemporary technologies, but there is still a problem of MT modules and indirectly of NLU and NLG modules. Current solutions of these modules enable work with limited dictionaries (which comprise all forms of used words) and due to this their application is restricted to certain domains such as: tourism, sport, health care, business, etc. There are a large number of very different patented solutions which solve translation from speech to speech. For example: U.S. patent 6,266,642 Bl, filed on January 20, 1999, under the title ,,Method and portable apparatus for performing spoken language translation", offers solution of translation from speech of one language into speech of another language combining two basic models of translation: model based on grammar rules (^'rule-based transfer" model) and model based on a large number of paired sentences of two languages ("example-based" model), as well as the procedure of correction of a wrongly recognized sentence; then, U.S. published patent application 2007/0016401 Al, filed on August 12, 2005, under the title ,,Speech-to-speech translation system with user modifiable paraphrasing grammars", offers specific solution of translation based on a phrase book, i.e. it transforms input sentences from a source language into basic canonic forms of phrases and translates them based on bilingual phrase book (dictionary), ignoring irrelevant variations of a source sentence; then, U.S. published patent application 2004/0024581 Al, filed on March 28, 2003, under the title Statistical machine translation", offers the procedure of statistical translation based on statistical models of a source language and a statistical model of translation, applying syntax segmentation of a source sentence into phrases (syntactic chunks); then U.S. published patent application 2004/0111272 Al, filed on December 10, 2002, under the title ,,Multimodal speech-to-speech language translation and display", which describes translation based on interlingua model with interesting symbolic and visual presentation of a source sentence after the processing in NLU module; then U.S. published patent application 2005/0049851 Al, filed on August 13, 2004, under the title ,,Machine translation apparatus and machine translation program", which offers the procedure of translation based on combination of example-based model and statistical model with the application of bilingual corpus of sentences and the choice of a sentence from translation into target language based on highest probability of similarity with the source sentence; then U.S. published patent application 2005/0010421 Al, filed on May 12, 2004, under the title ,,Machine translation devices program", which describes the procedure of multilingual translation based on interlingua model where in one case English language appears as interlingua, and in the other case abstract semantic structure; then U.S. published patent application 2004/0002848 Al, filed on June 28, 2002, under the title ,,Example-based machine translation system", which describes system for translation based on classical example-based model.

For Serbian language there is only one patent, Serbian national patent P-343/04, filed on April 24, 2004, under the title ,,System and method for machine translation of conversational speech from Serbian into English", which offers a solution of machine translation of spoken Serbian language into spoken English language and falls into category of machine translators based on grammar rules.

Disclosure of the Invention Subject of this invention is system for translation of the speech from one language into the speech of another language, which is organized on the new method based on interlingua domain which enables multilingual realization of translation, with an example of the procedure of translation from Serbian language into English language. Considering the application of this system for translation of conversational speech, it is necessary to realize two premises: (i) conversation with short sentences of a type subject-action-object (if speaker's utterance is longer, then it can be realized from successive translation sentence by sentence) and (ii) conversation with grammatically correct and complete sentences.

System, which is the object of the invention, is based on the universal approach which represents generalized form of interlingua model. Namely, interlingua models assume existence of interlingua which can be either one of natural languages (e.g. English; also, there were attempts to use Esperanto (Witkam, T., (1988). DLT - an industrial R&D project for multilingual machine translation. In Proc. of the 12^th International Conference on Computational Linguistics, Budapest) or one of machine languages. This invention does not require the use of a natural or artificial interlingua - instead, interlingua domain is formed containing all the necessary information needed for the synthesis of a target language (in the ideal case of any language). Interlingua domain contains two conceptually different modules: (i) Interlingua Reservoir of Concepts IRC and (ii) Interlingua Bank of Bilingual Dictionaries IBBD. All information obtained by analysis of language structure of input sentence of the source language is collected in IRC module, which should be sufficient for sentence synthesis in any target language. Certainly, this synthesis is not possible without bilingual dictionaries which are memorized in IBBD module.

Therefore, the essence of interlingua domain is to define and provide all language information and concepts on the basis of which utterance (sentence) in a chosen language can be generated. Such approach to the solution of translation in this invention requires three things from each language which accesses interlingua domain: (i) complex and complete language analysis of an input sentence and identification of all information and concepts (of lexical, syntax, semantic, structural, etc. type) which are memorized in IRC module, (ii) standardized and structured bilingual dictionaries for each language with which source language wants to be in contact, which are filed in IBBD module, and (iii) sentence synthesis based on all information from interlingua domain with the use of own grammar (when given language is in the function of target language).

Specific aspect of the invention is the realization of the system based on the access of Serbian and English to interlingua domain and translation of Serbian sentence into English sentence. In such solution, Serbian language appears as source language, and English appears as target language. The next particularity of the invention is the speech-language analysis of sentence in Serbian language with the application of monolingual dictionaries of limited volume (monolingual annotated dictionary and monolingual phrase dictionary). This analysis assumes three functionally different, but structurally very connected basic modules: (i) module for automatic speech recognition (module ASR), i.e. text-to-speech conversion; (ii) module for language analysis of the source sentence with the aim of recognition and identification of its constituents and their functions and meanings, as well as analysis of sentence structure and its semantic attributes (module NLU); and (iii) module for generation of correct source sentence which, in spontaneous speech, can very often be incomplete, grammatically incorrect or inexplicit (module NLGs).

This invention is specific because of the new procedure of identification of phrases in the source sentence. Unlike the solution given in the above mentioned patent P-343/04, filed on April 24, 2004, under the title ,,System and method for machine translation of conversational speech from Serbian into English", where the search of the phrase in the sentence was performed unilaterally and where there was a possibility of absence of phrase identification, we applied the procedure of complete search and absolute identification.

The next particularity of the invention is the new procedure of restructuring the input sentence. The procedure is based on the theory of graph and solving generalized problem of traveling salesman. In the graph, which is joined to the input sentence, each word represents one supernode, and each syntax meaning of the word one subnode (each word in the sentence is given one ore more syntactic meanings). Each subnode can have, but does not have to, the connection with other subnodes of other supernodes. The mentioned connections are obtained on the basis of grammar rules of connecting syntactic meanings of words. Analysis of the sentence structure is performed by traveling salesman that should visit all supernodes passing through one subnode of each supernode at the most.

Functioning of NLGs module represents distinct specificity in this invention. Namely, the aim of this module is to reversibly present speaker with his/her sentence, corrected and transformed into a completely correct form which, on the one hand, does not impair initial meaning of the sentence and, from the other hand, provides the best quality translation into target language. Module NLGs uses all information after NLU analysis and generates correct sentence in source Serbian language. Synthesis or generation of a sentence in the target language, module NLG_T, is the next specificity of the invention. Functioning of this module is highly complex because it uses all grammar rules of the target language, and its specificity is reflected in the usage of information from interlingua domain as starting parametres in generation of target sentence. Finally, particularity of the invention can be also found in the interaction of NLG_T module and TTS module in the increase of the quality of synthesis in target language. Namely, certain information from NLG_T module can be used for the control of prosody of TTS module.

Resourcefulness of this invention lies in the improvement of each of the stated particularities and originality of some solutions within certain modules, but also in the procedure of integration of all modules into a unique entity with stable, quality functioning.

These and other aspects, particularities and benefits of this invention will be more obvious after the insight into a detailed description of the invention, patent dims and related drawings. Brief Description of the Drawings

Figure 1 - Basic concept of the system for multilingual translation from speech to speech. Figure 2 - Basic scheme of source language approach to interlingua domain. Figure 3 - Detailed block scheme of NLU module for the analysis of Serbian (source) sentence.

Figure 4 - Syntax meanings of words in the sentence ,,Limeni krov odnela je snazna oluja" (Strong storm blew off a tin roof).

Figure 5 - Model of affirmative sentence. Figure 6 - Model of negative sentence.

Figure 7 - Model of interrogative sentence. Figure 8 - Model of interrogative-negative sentence. Figure 9 - Model of ,,WH" interrogative sentence.

Figure 10 - Basic graph of the sentence ,,Limeni krov odnela je snazna oluja" (Strong storm blew off a tin roof) .

Figure 11 - Traveling salesman path for the sentence ,,Limeni krov odnela je snazna oluja" (Strong storm blew off a tin roof) and grammatical description of all the words in the sentence.

Figure 12 - Syntax meanings in the sentence ,,Veliki posao sam dobro uradio" (I did a big job well).

Figure 13 - Basic graph of the sentence ,,Veliki posao sam dobro uradio" (I did a big job well).

Figure 14 - Traveling salesman path for the sentence ,,Veliki posao sam dobro uradio" (I did a big job well) - solution I: ,,Sam uradio dobro veliki posao". Figure 15 - Traveling salesman path for the sentence ,,Veliki posao sam dobro uradio" (I did a big job well) - solution II: ,,Sam uradio veliki posao dobro".

Figure 16 - Tables for formal description of sentence meaning.

Figure 17 - Tables for formal description of the meaning of the sentence "Limeni krov odnela je snazna oluja" (Strong storm blew off a tin roof). Figure 18 - Tables for formal description of the meaning of the sentence "Sam uradio dobro veliki posao".

Figure 19 - Structure of interlingua domain.

Figure 20 - Basic scheme of generating sentence in English (target) language based on information from interlingua domain. Figure 21 - Models of English sentences.

Figure 22 - Structure of English translation of the sentence ,,Limeni krov oduvala je snazna oluja" (Strong storm blew off a tin roof). Best Mode for Carrying Out of the Invention

This invention describes the system and method for multilingual translation from speech in the source language into speech in a number of target languages. Multilingualism is provided by the concept of interlingua domain which contains all necessary information for generating sentence of a chosen target language and conversion into speech signal.

Figure 1 shows basic concept of the system for multilingual translation. The basis of this concept is interlingua domain (ID), 101, which is accessed via access points (AP)₅ 102, in general case, with random number of speech signals in different languages, 103 to 106. Processing of each speech in mother tongue is two-way: towards interlingua domain and from interlingua domain. For example, in the block 103 processing of speech signal is performed in the first language with the aim of recognition and conversion to text, and language analysis of the text in order to obtain all the information necessary for translation into another language. Via access point AP these information are memorized in the module - interlingua reservoir of concepts (IRC), which is one of the basic parts of interlingua domain, 101. In the opposite direction, when we translate from the second language into speech of the first language, information from the module - interlingua reservoir of concepts (IRC), interlingua domain, 101, are taken over by the block 103 where the sentence is generated based on grammar rules of the first language, which is then converted into speech signal.

Interlingua domain, 101, contains another module - interlingua bank of bilingual dictionaries (IBBD), which files bilingual dictionaries of one language in contact with other languages which are included in projected system for translation. Module IBBD contains two types of bilingual dictionaries for each pair of languages, bilingual annotated dictionary and bilingual phrase dictionary, which regarding content must be in complete accordance with monolingual dictionaries of both languages. Both bilingual dictionaries have two versions because translations are not symmetrical due to possible different meanings of the same word in both languages; this fact is particularly expressed in a phrase dictionary. Concept of the system for multilingual translation given in Figure 1 is of modular type. This means that the system can be expanded by a new subsystem for a new language by a new access point 102. On the side of the new language, new subsystem contains speech-language analysis of input speech towards interlingua domain (direction towards the target language) and speech language synthesis of output speech from interlingua domain (direction from the target language). Within interlingua domain (ID), 101, new subsystem reserves in the module interlingua reservoir of concepts (IRC) memory space for information extracted by language analysis of a new language, and memory space in the module interlingua bank of bilingual dictionaries (IBBD), for storing bilingual dictionaries which connect new language with other languages which are in IBBD module and which are intended for the realization of the function of translation. This invention solved one-way translation from Serbian language into English language, i.e. it solved access to interlingua domain for Serbian language and access from inter lingua domain for English language.

Figure 2 shows block scheme of solutions of the analysis of source sentence in Serbian language. The first speaker's activity 201 in Serbian (source) language is the choice of a language into which he wants the operation of translation to be performed, English (target) language. This command is forwarded to interlingua domain 202, where module IBBD, interlingua bank of bilingual dictionaries, performs choice of corresponding bilingual dictionaries of a pair of languages, Serbian - English. Content of bilingual dictionaries define the volume of a dictionary and the domain of the application of the system for translation. In this way the system is prepared to perform the operation of translation.

Speaker pronounces the sentence he wants to be translated by the system. By a microphone, a speech signal is introduced into module 203 for speech recognition and its conversion to text, module ASR. Recognition is performed within a dictionary whose volume and content is determined by monolingual dictionary of Serbian language 204. If module ASR cannot recognize the pronounced word for any reason (incorrectly pronounced word, exceeded level of noise at recording, out of vocabulary word OOV, etc.), speaker is sent a warning with the request to pronounce the same word again or a new word.

Due to the complex morphology of Serbian language, ASR module can make frequent mistakes in recognition of words with a different final vowel, such as in declensions of noun words according to case (e.g.: pesma, pesmi, pesme, pesmo, pesmu) or in conjugations of verbs according to person, gender and number (e.g.: pisalo, pisala, pisala pisali). Although ASR module is realized based on hidden Markov models (HMM), acoustic model of speech and model of language, ASR makes the mentioned mistakes due to the effect of devocalization of the last sound in a word in training ASR modules by means of isolated words. These mistakes are of systematic nature and they can be statistically corrected by the formation of a list consisting of n words ranked according to a posteriori probability, i.e. probability that exactly these words were pronounced.

Recognized sentence is transferred from module 203 to module 205, the block NLU, where complete language analysis is performed. NLU module performs analysis of words and phrases in the input sentence, syntactic and semantic analysis, as well as lexical corrections if the input sentence is incomplete. For this analysis of NLU module information are needed from monolingual annotated dictionary, module 204, monolingual phrase dictionary, module 207, and grammar of the source Serbian language, module 206. Words and phrases from monolingual dictionary are temporarily memorized in INTERFACE BUFFER, module 208, and used to prompt bilingual dictionary in interlingua domain, module 202. NLU module will be described in detail later. Output information from NLU module give complete grammatical and semantical description of the input sentence, which was previously corrected, completed and brought to a standard form suitable for translation into other languages; i.e. free form of a Serbian sentence is transformed into one of standardized forms used in this invention. These information are temporarily memorized in INTERFACE BUFFER, module 208, where they are stored until user A confirms or denies their correctness. The same information are forwarded to module NLGs, marked 209, where generation (or synthesis) of a corrected sentence is performed. Synthesized sentence is then presented to the user (speaker A) 201 for verification. This presentation can be visual, via display, or auditory, which can be more operational, using the block 210 for text to speech synthesis, the block TTS. User's task is to check whether all the changes in his sentence made by the system do not change the sense that he wanted to convey to conversationalist in the target language. If the user estimates that the meaning of an initial sentence is unchanged, he activates the command 'TRANSLATE' by which all information temporarily memorized in module 208 are transferred to inter lingua domain 202. If the user is not satisfied, NLU module will offer alternative meaning, if there is one. If the user is still not satisfied, then the same thought should be replaced with the new, simpler, and possibly shorter sentence.

The solution of this invention anticipates the possibility of promoting speech synthesis in the target language in the sense of quality of synthesized speech. With that aim, in the speech of the source language paralinguistic information can be identified, being the consequence of psycho-emotional state of the speaker. These information can be identified directly in the speech signal at the system entrance, but also during language analysis in module NLU. Function of identification of paralinguistic information is performed in the block 211, and the result of analysis is memorized in interlingua reservoir of concepts, the block 401 (Figure 19).

Figure 3 shows the diagram of the course of operations u module NLU, module 205. In the block 300, in the input sentence identification of words and phrases is performed first, and then in the block 301 their syntactic meaning is determined by the use of monolingual annotated dictionary 302 and monolingual phrase dictionary 303.

Monolingual dictionary 302 contains certain number of words in the basic form and in all grammar forms. Each of these forms in a dictionary appears as separate lexeme with complete grammatical description. Figure 4 gives an example of grammatical description of such formulated lexeme. Dictionary also contains homonyms as separate lexemes, with additional description of semantic meaning. Phrase dictionary 303 contains phrases and all their grammar forms, with similar grammatical description as well as words.

In this invention, identification of phrases within the sentence is performed by new algorithm, much better and more successful compared to the same one given in patent P- 343/04, filed on April 24, 2004, under the title ,,System and method for machine translation of conversational speech from Serbian into English". Whereas in patent P- 343/04 phrase detection was performed by the method of shortening sentences from the right side, due to which there was a possibility of omission some of the phrases, in this patent the complete search is applied, according to all possible lengths of phrases and according to all possible positions of a phrase in the source sentence. The search proceeds from the assumption that the whole sentence represents one phrase. If the assumed phrase in that form is found in the dictionary, the whole sentence is declared a phrase. In the opposite case, we proceed to the next step - finding phrases which are one word shorter compared to the search in the previous step. The search is performed according to all positions in the source sentence. If the phrase is identified in one of the positions, belonging words are labeled as identified part of the text, i.e. phrases, and the search process is continued on the remaining unidentified part of the text. In the next step on the remaining part of the text, in the same way the presence of phrases is tested, which are one word shorter compared to the previous step of the search. In the last step, certain words are identified with the help of annotated monolingual dictionary in the remaining unmarked part of the text.

Example of phrase identification:

At the entrance to the block 300 we have an affirmative sentence ,,Prijatelji, dobar dan svima" (Friends, good day to all) which has 4 words and contains the phrase 'dobar dan' (good day). prijatelji dobar dan svima

(friends) (good) (day) (to all)

1 2 3 4

Step 1 We check whether in the text consisting of 4 words there is a phrase of 4 words, i.e. whether the whole sentence represents one phrase. The answer is NO. Step 2 Now we examine the phrases which are one word shorter, i.e. they have 3 words. We check whether word string (1-3) 'prijatelji dobar dan' is found in phrase dictionary. The answer is NO.

We check whether the word string (2-4) ('dobar dan svima') is found in phrase dictionary. The answer is NO. Step 3 Now we examine the phrases which are one word shorter, i.e. they have 2 words. We check whether word string (1-2) 'prijatelji dobar' is found in phrase dictionary. The answer is NO. We check whether word string (2-3) is found in phrase dictionary. The answer is YES, because the dictionary contains the phrase 'dobar dan'. Now the initial sentence is presented with three elements: prijatelji dobar dan svima

(friends) (good day) (to all)

1 2 3 word phrase word

The second element is the identified phrase.

Step 4 The search is continued on the text which has not yet been marked as identified. These are words 'prijatelji' and 'svima'. They can be found as single words in a monolingual annotated dictionary 302. This completes the search. Analysed sentence contains 3 elements given in the table: prijatelji dobar dan svima

1 2 3 word phrase word Due to word polymorphism, as well as the fact that some different case forms and other forms have the same inflectional suffixes, it is often the case that the same word transcription has more different meanings. Monolingual dictionary 302 offers all possible meanings of certain word transcriptions, which are singled out and treated as possible hypotheses. By the application of certain grammar rules, certain hypotheses in the following phases will be rejected as grammatically or logically incorrect, and only one or two possibilities will remain. Figure 4 gives an example of the sentence ,,Limeni krov odnela je snazna oluja" (Strong storm blew off a tin roof.) with presented possible meanings of each word. Word 'limeni' (tin) appears as an adjective in four forms determined by number and case, whereas words 'krov' (roof) as a noun and 'snazna' (strong) as an adjective appear in two forms determined by cases; remaining words 'odnela' (blew off), 'je' (AUXILIARY VERB) and 'oluja' (storm) are in one form. Therefore, in the sentence of 6 words there are 11 word forms.

In the block 304 analysis of the input sentence structure is performed based on the comparison with the adopted models of the sentence in Serbian language which is in the block 305, and which are formed based on grammar of source (Serbian) language, the block 306. This procedure is very important because at the very beginning of the analysis in NLU block, input sentence, which can be incomplete, incorrect or inaccurate, is categorized according to sentence type and arranged into one of standardized forms which are adjusted to machine translation.

The block 305 contains models of sentences for Serbian language. Figures 5 - 9 show models of the following types of sentences: affirmative sentence, negative sentence, interrogative sentence, interrogative-negative sentence and ,,WH" interrogative sentence. Other models can also be added to this bank of models. Each model consists of certain number of modules which mark a word or a group of words with certain function in the given sentence. Within the model, most frequent connections between modules are allocated, and example sentences illustrate usability of the model.

Models of sentences are structured so as to meet the following demands:

1) To cover basic types of sentences (affirmative, negative, interrogative, interrogative-negative, real question).

2) To be in accordance with grammar of Serbian language.

3) Models are defined in such a way that every separate sentence, by permutation of word, can be described by one of defined models.

4) Models should cover cases of incomplete sentences, i.e. sentences with omitted, but clearly implied elements.

5) Models should be such that in the largest possible number of cases, preferably always, connection of sintactic meanings of two adjacent words in a sentence depend solely on themselves, and not on the preceding words. In other words, in the applied models the formed word string should have Markov property of the first order. This is an important characteristic which enables the sentence to be assigned the corresponding graph of connection which would be in absolute accordance with the grammar of the language. 6) Models should be such that they can provide a simple way for obtaining standardized (multilingual) format of the description of the meaning of the sentence.

Basic structure of all models is SUBJECT GROUP + PREDICATE GROUP₅ and within predicate group VERB + OBJECT. Therefore, basic structure of all models is SUBJECT + VERB + OBJECT.

The second particularity of all models is the position of attribute, auxiliary verb, adverb and adverbial in the sentence structure: attribute always precedes a noun, auxiliary verb always precedes a verb, adverb always precedes an object, and adverbial is always at the end of the sentence. Thereby, each sentence unit can contain more words, an example of attribute 'znamenita, star a i oronula kuca' (famous, old and dilapidated house), or it can be omitted from the sentence.

The third particularity of models is the difference between interrogative forms of the sentence and other forms. Interrogative forms of the sentence in the initial position have interrogative syntagms or pronouns.

In free communicative form Serbian sentences can omit some forms of the words, which are mostly implied, or the sentence structure can significantly deviate from the given models. The task of NLU module is to recognize, identify and complement all these variations, and complete the sentence according to the models in the block 305, without changing the meaning of the source sentence. The first step in this procedure is performed in the block 304.

Functioning of the block 304 is based on the new and specific method of restructuring the input sentence. The method is based on the graph theory and solving generalized problem of traveling salesman (Dimitrijevic, V., & Saric, Z. (1997). An efficient transformation of the generalized traveling salesman problem into the traveling salesman problem on digraphs. Informatics and Computer Science 102, 105-110.). In the block 301 each word in the sentence is given one or more syntactic meanings. In the graph, which is joined to the input sentence, each word represents one supernode, and each syntactic meaning of the word one subnode. Each subnode can have, but need not have, connections with other subnodes of other supernodes. Analysis of sentence structure is performed by traveling salesman who should visit all supernodes passing through only one subnode of every supernode at a time.

Graph of (possible) connections of subnodes is obtained based on grammar rules of connecting syntactic meanings of words. In the first example given in Figure 4, for the sentence ,,Limeni krov oduvala je snazna oluja" (Strong storm blew off tin roof), we shall assume that the sentence is affirmative and in its further analysis model of an affirmative sentence from Figure 5 will be used. Previously, by means of module 301 a table was formed of possible meanings of each individual word, Figure 4. After that, branches of graph are formed which connect nodes according to grammar rules of possible connections of syntactic meanings of words, as well as assumed sentence model. Supernodes will be marked by numbers, and subnodes with indexes. Example I: Forming graph of connection of words/meanings

I₁ is connected to 2 ! - Nominative of singular adjective 'limeni' (tin) agrees in case, gender and number with nominative of singular of a word 'krov' (roof). 1₁ is connected to 4i Nominative of singular adjective 'limeni' (tin) can precede contracted form of the verb to be in the third person singular. I₂ is connected to 2₂ Accusative of singular adjective 'limeni' (tin) agrees in case, gender and number with accusative of singular of a word 'krov' (roof). 1₃ no connections - Nominative of plural of adjective 'limeni' (tin) does not agree with any of the nouns in the sentence. I₄ no connections ^■ Vocative of plural of adjective 'limeni' (tin) does not agree with any of the nouns in the sentence.

2i !→ li In grammatical sense, this connection is possible, but it does not correspond to the adopted model of an affirmative sentence where the attribute comes before the noun.

2₂ !-» 1: In grammatical sense, this connection is possible, but it does not correspond to the adopted model of an affirmative sentence where the attribute comes before the noun. 2i !→ 3i In grammatical sense, this connection is possible, but it does not correspond to the adopted model of an affirmative sentence where noun (subject) goes before auxiliary verb, which is followed by present participle active which should agree with the noun (subject). Connection SUBJECT — > ACTIVE PARTICIPLE is not allowed. In this case, they even do not agree in gender.

2_\ is connected to 4i - Noun in nominative (subject) can be followed by auxiliary verb 'is'. This is how Perfect tense is formed, as well as Present tense, e.g. 'krov je lep' (roof is nice). Connections (2_t -» 50 and (2i -» 6j) Not possible.

3i !-» I i According to the adopted structure of affirmative sentence, predicate cannot be followed by noun word in nominative.

Possible variant would be 'je limeni (krov)' (is tin (roof)) - nominative as subject complement. 3i is connected to I₂ - Word 'limeni' (tin) in accusative after predicate (verb) has the function of object or object complement.

3i !→ 2i According to the adopted structure of affirmative sentence, predicate cannot be followed by noun word in nominative.

Possible variant would be 'je krov' (is roof) - nominative as subject complement.

3₁ is connected to 2₂ - Word 'krov' (roof) in accusative after predicate (verb) has the function of object. 3i ! — > 4i - According to the adopted structure of affirmative sentence, auxiliary verb is followed by present participle active. The opposite is not possible.

3i ! — > 5i - According to the adopted structure of affirmative sentence, predicate is followed by an object, not nominative.

Nominative is possible only in the combination [auxiliary verb 'je' (is) -» nominative] when nominative has the role of subject complement.

3] !-> 6) - According to the adopted structure of affirmative sentence, predicate is followed by an object, not nominative.

Nominative is possible only in the combination [auxiliary verb 'je' (is) — > nominative] when nominative has the role of subject complement. (4! → I ₁), (4_t → 20, (4i → 50, (4i → O₁) - All these connections exist, noun word in nominative having the role of subject complement. (4i — > 30 - This is Perfect verb form.

(βι -> 40 - In this case, adjective has the role of subject (replacing the noun in nominative). (6i -» 40 - According to the adopted structure nominative (subject) is followed by auxiliary verb which represents predicate or forms complex verb form. (O₁ !— > 3i) - This combination is grammatically possible, but according to the adopted structure of affirmative sentence, present participle active is preceded by auxiliary verb.

Previous analysis established possible connections in the graph of an initial sentence. Graph given in Figure 10 is formed based on these connections.

Opened path of the traveling salesman should include all supernodes (words) from 1- 6. In the general case, more different paths are possible for the following reasons:

1) Sometimes there are more formally correct meanings of sentences, but some of them might be meaningless.

2) Some paths, although formally complying with the introduced limitations of connecting word meanings, can be grammatically incorrect. The reason for this is that the graph is formed based on Markov property of the first order, which sometimes does not hold when language is in question.

Typical example of a stated problem 2) is the case of complex Perfect tense, where subject's gender and number influences the form of present participle active, which follows the verb to be. Or reversely, form of present participle active does not depend only on the previous word (auxiliary verb to be) but also on the gender and number of noun word before auxiliary verb which has the role of a subject. This patent suggests that if there are more paths in a graph, additional grammar check of each path is needed, and grammatically incorrect should be discarded. Grammar check is related to checking agreement of corresponding grammar units in person, gender and number for verb forms, and agreement in case, gender and number for subject units.

Figure 11 shows optimal path which as a solution gives a sentence of the following form ,,Snazna oluja je oduvala limeni krov"; input sentence was ,,Limeni krov oduvala je snazna oluja".

Example II

Example of a sentence „ Veliki posao sam dobro uradio" (I did a big job well) is characteristic for omitted subject. Figure 12 shows the given possible meanings of words. As well as in the previous example, we shall assume that the sentence is affirmative and try to determine connection of graph nodes based on grammar.

Ii is connected to 21 Nominative of singular adjective 'veliki' (big) agrees in case, gender and number with nominative of singular of a word 'posao' (job). Ii is connected to A_\ Nominative of singular adjective 'veliki' (big) can precede contracted form of the verb to be in the third person singular. Example: ,,Veliki sam umetnik". (I am a big artist)

I₂ is connected to 2₂ Accusative of singular adjective 'veliki' (big) agrees in case, gender and number with accusative of singular of a word 'posao' (job).

I₃ no connections - Vocative of plural of adjective 'veliki' (big) does not agree with any of the nouns in the sentence.

2, !→ 1 , In grammatical sense, this connection is possible, but it does not correspond to the adopted model of an affirmative sentence where the attribute comes before the noun.

(2₂ !-> I₂) In grammatical sense, this connection is possible, but it does not correspond to the adopted model of an affirmative sentence where the attribute comes before the noun.

(2i !→ I₃) This connection is not possible. (2i !→ 30 According to the adopted sentence structure, this connection would assume that 'posao' (job) is a subject, and 'sam' (am) is an auxiliary verb 'to be'. Due to agreement in person, instead of 'sam' (am) there should be 'je' (is). Since that is not the case, this connection is not possible. (2, !-> 4,) This connection is not possible. Possible connection would be ,,Posao ide dobro" (Job is going well), meaning that an adverb of manner cannot be placed right after the subject in nominative.

(2, !-> 50 This connection is not possible because present participle active cannot be placed right after the noun in nominative. (2₂ !→ I₂) This connection is not possible because of the adopted sentence model in which an adjective describing an object always precedes that object.

(2₂ !→ 3i), (2₂ !-> 3₄) ^• These combinations obviously are not possible for a number of reasons.

(2₂ is connected to 4_t) Object can be followed by adverb of manner, as e.g. in a sentence ,,Radim posao dobro" (I am doing my job well).

(2₂ !→ 50 Noun in accusative (object) cannot be followed by present participle active. (3 ] is connected to I₁) - Noun/adjective in nominative represents subject complement when positioned after auxiliary verb 'to be'. (Functions of nominative in the sentence.)

(31 is connected to 2j) - Noun/adjective in nominative represents subject complement when positioned after auxiliary verb Ho be'. (Functions of nominative in the sentence.)

(3i is connected to 4i)- Adverb of manner can follow auxiliary verb 'to be' and then it has the function of an adverbial. (S₁ is connected to 5i) - Auxiliary verb 'to be', followed by present participle active, forms Perfect tense. (4i is connected to I2) Adverb of manner, which is a predicate complement, can be followed by adjectival part of an object (in accusative).

(4i is connected to 2₂) - The same reason as for (4i,l₂) (4i !→ 3i) Although it is gramatically correct, there are no connections, because due to an adopted model 'dobro sam' should be replaced with '(ja) sam dobro' ((I) am well).

(4i !-> 5,) Although it is grammatically correct, there are no connections, because due to an adopted model adverbial should follow the predicate.

(5i is connected to I₂) - Connected as an object which follows the predicate. (5i is connected to 2₂) - Connected as an object which follows a predicate. (5i !→ 3i> Although it is grammatically correct, there are no connections, because due to an adopted model there should be 'sam uradio' instead of 'uradio sam'. Namely, according to an adopted model auxiliary verb 'to be' precedes present participle active, and not vice versa.

(5_\ is connected to 4i)~ Adverbial of manner can follow present participle active.

This is grammatically correct, and at the same time it is in accordance with adopted sentence model.

Figure 13 shows graph of this sentence with possible connections. One of the possible paths is given in Figure 14, which corresponds to rearranged sentence ,,Sam uradio dobro veliki posao". The solution is not unique, i.e. there is another solution, given in Figure 15, which transforms the initial sentence into ,,Sam uradio veliki posao dobro". Both solutions are equivalent, given that in both cases the meaning of the initial sentence is preserved.

Further analysis of the sentence is performed in the blocks 307, 308 and 309. In the block 307 sentence parsing is performed, Le. function of words in the sentence is determined; in the block 308 insertion is performed of omitted but implied words in spoken Serbian language, such as pronouns, using catalogue of these words 310; and in the block 309 semantic analysis is performed, firstly on the level of lexical semantics, and partly on the level of sentence semantics.

After all these analyses, transformed form of input sentence is finally formed in the block 311 and after establishing success or failure of locating input sentence within

Serbian grammar and adopted models in this invention, which is performed in the block

312, in case of a negative answer (NO), result of the analysis is forwarded to the user with the request to pronounce the input sentence again in a different but correct manner and in case of a positive answer (YES) block 313 is approached where all information definitely accumulate which are necessary for the formal description of the input sentence which is forwarded into interlingua domain 202 (Figure 2) via INTERFACE BUFFER, module 208

(Figure 2).

Considering the role and significance of the block 313 in the phase of analysis of the source Serbian sentence, its content will be described first. Content of the block 313 is given in Figure 16 and it contains all the information obtained by analysis of the source sentence. FORMAL DESCRIPTION OF SENTENCE MEANING implies the set of all information on the meaning (sense) of the source sentence so that it can be translated into any language. Formal description contains three components: sentence type, description of subject and description of predicate group, and they are given in Figure 16 in the form of tables. Content of these tables is changeable, which depends on the content of the analysed sentence.

Data on the recognized sentence type and on the key syntagm on the basis of which the sentence type is determined, according to models of the sentence given in Figures 5 to 9 are entered in the table SENTENCE TYPE. All information after parsing related to each word, its form and part of speech, function in the sentence, tense, function of word group, etc. are entered in tables SUBJECT GROUP and PREDICATE GROUP.

Functioning of the blocks 307 to 313 will be demonstrated on the example of previous sentences. Example IH

Let us take the transformed sentence ,,Snaέna oluja je oduvala limeni krov" (Strong storm blew off the tin roof). Description of this sentence is given in Figure 11. Since model of an affirmative sentence was applied and it gave adequate solution, this is at the same time confirmation that the initial sentence is affirmative. This datum is entered in the table SENTENCE TYPE in Figure 17. After this, the predicate is to be determined. Initial assumption is that sentence contains verb predicate (predicate can be both noun and adverbial). Presence is checked of one of auxiliary verbs ('jesam', 'biti' - both meaning 'to be') which form complex tenses. The search result is that in position 3 there is contracted form of the verb 'to be' in the third person singular, and that in position 4 there is present participle active feminine gender singular. Based on these data it is concluded that Perfect is a figurehead in the sentence. All these data are entered in the table PREDICATE GROUP in Figure 17.

Further analysis shows that auxiliary verb 'to be' is preceded by the noun 'oluja' (stoπn) of feminine gender in nominative. Since this noun agrees in gender and number with present participle active 'oduvala' (blew off), and in person and number with auxiliary verb 'to be', it follows that the noun 'oluja' (storm) is the subject. Word 'oluja' (storm) is preceded by the adjective 'snazna' (strong) which agrees with it in case, gender and number. Thus, it follows that the word 'snazna' (strong) has the role of an attribute. All these data are entered in the table SUBJECT GROUP, in Figure 17.

The remaining two words 'limeni' (tin) and 'krov' (roof) characterize the object in the sentence and object attribute, since both words are of masculine gender in accusative singular. These data complete the table PREDICATE GROUP.

This finalizes the procedure of parsing and forming formal description of meanings.

Example IV

Description of the words in a sentence „ Veliki posao sam dobro uradio" (I did a big job well) is given in Figure 14. In the block 304 it is restructured in the form u ,,Sam uradio dobro veliki posao" according to the model in the affirmative sentence in Figure 5. This datum is entered in the table SENTENCE TYPE in Figure 18. In the same way as in the previous example, first the predicate is identified, which is also in Perfect tense. It consists of the contracted form of auxiliary verb 'to be' and present participle active 'uradio' (did). This datum is entered in the table PREDICATE GROUP in Figure 18. It is determined that in front of auxiliary verb 'to be' the noun in nominative is missing, as well as a pronoun which could play the role of a subject; apposition is missing as well. Based on the first person singular of auxiliary verb 'to be' and masculine gender of present participle active it is concluded that pronoun 'ja' (I) is omitted. This datum is entered in the table SUBJECT GROUP, in Figure 18, instead of a missing subject. Further analysis determines adverb of manner 'dobro' (well), object 'posao' (job) and its attribute 'veliki' (big). These data are entered in the table PREDICATE GROUP.

This finalizes the procedure of parsing and insertion of omitted, but clearly implied pronoun 'ja' (I). New, transformed sentence should be worded: "Ja sam uradio dobro veliki posao". According to Figure 3, information on formal description of the source sentence are forwarded to module NLGs, module 209 (Figure 2). Function of this module is twofold: primarily, it should generate (synthesize) the source sentence which has been corrected based on analytical procedures and models of sentences formulated in this invention, with the aim of enabling the user with final insight into correct functioning of the system for translation and its final confirmation that process of translation can continue towards the target language, and secondarily, with this function module NLGs verifies validity of formal description of the source sentence. Functioning of NLGs module is independent of the model of sentences adopted in the phase of the analysis of input sentence. As indicated previously, these models do not reflect actual structures of Serbian sentences - they are maximally formalized and conformed to the idea of interlingua domain. Therefore, processes which are completely inverse to processes in module NLU do not develop in module NLGs - the sentence is synthesized according to models corrected in the spirit of natural Serbian language. For example, after analysis, parsing and transformation, sentence ,,Ja sam uradio dobro veliki posao" (I did a big job well) at the exit of NLGs module should be worded ,,Ja sam dobro uradio veliki posao" (I did well a big job). Obviously, in the largest number of cases difference between input and output sentence in NLGs module should be reflected in corrected word order.

Also, information on formal description of the sentence are forwarded via INTERFACE BUFFER, module 208 (Figure 2), to interlingua domain, module 202 (Figure 2), and memorized in interlingua reservoir of concepts (IRC). Structure of interlingua domain (ID) is given in Figure 19. In interlingua reservoir of concepts IRC (module 401) formal descriptions of sentence meaning in the source language, in this case Ll - Serbian language are memorized in module 403. Naturally, similar information for all other languages which are incorporated in the system of translation are also memorized here. Besides these information, special field of memory is intended for paralinguistic information, the block 407, identified in the source language.

All information from module 403 and interlingua bank 402 of bilingual dictionaries IBBD, annotated words 404 and phrases 405, come to module 406 where recognized sentence meaning in source (Serbian) language is transformed into target (English) language. Original meaning of each word in the source language is 'translated' into one or more meanings of the target language. In cases when certain words have more than one meaning in translation, selection of meanings is performed in module NLGT of the target language based on the following criteria:

1. Based on the grammar rules of the target language.

2. Based on the probability of the occurrence of certain translations in the corresponding domain of usage of the system for translation. Domains can be: tourism, sport, science, politics, education, traffic, history, etc.

Elimination of polysemy of the translation of certain words can be realized by solving problems of generalized traveling salesman on the graph joined to the sentence in a similar way as explained in the description of the block 304, in this case subnodes being potential translation of words into English language.

In NLGT module, module 500 (Figure 20), generation of English sentence is performed using the following data:

1. Universal description of the meaning of an initial sentence which was previously formed in NLU module. 2. Using all relevant translations of the words of initial sentence obtained on interlingua level by the application of phrase dictionaries and annotated dictionary.

3. Using adopted models of an English sentence, module 503. 4. Using grammar rules for the formation of sentence in English language, modules

501 and 502. In further text, following abbreviations were used:

S - Sentence NP - Noun phrase

VP - Verb phrase

PP - Prepositional phrase

N - Noun

V - Verb AUX - Aauxiliary verb

DET - Definite/indefinite article (determiner)

P - Preposition

ADV - Adverb

ADJ - Adjective Models for the synthesis of an English sentence are formed according to following rules:

1. Sentence (S) is formed from a noun phrase (NP), auxiliary verb (AUX) which can be omitted, and verb phrase (VP)

S → NP (AUX) VP

2. Verb phrase (VP) consists of a verb (V), noun phrase (NP) which can be omitted, and prepositional phrase (PP) which can be repeated more than once.

VP -> V (NP) PP*

Asterisk denotes that an element can be repeated a number of times, but at the same time does not have to appear at all.

3. Noun phrase (NP) can, but does not have to contain definite and indefinite article (DET), can, but does not have to contain adjective (ADJ) and definitely has to contain (N) (or pronoun)

NP → (DET) (ADJ) N

4. Prepositional phrase (PP) contains preposition P and new noun phrase (NP).

PP → P NP Based on these rules, structure of the model of an affirmative sentence is given in

Figure 21a. In its generation, natural word order is used according to the formula: subject + predicate + (direct object + (indirect object) + adverb of manner) + (adverb of place) + (adverb of time)

Using the example of translation of Serbian sentence ,,Limeni krov oduvala je snazna oluja", with English translation ,,Strong storm blew off a tin roof, we get the sentence tree given in Figure 22.

According to grammar of English language, interrogative sentence is formed by placing an auxiliary verb in the beginning of the sentence as given in Figure 21b. According to the stated rule, affirmative sentence from the previous example is transformed into the following interrogative sentence ,,Did strong storm blow off a tin roof.

Negative sentence is formed by placing auxiliary verb before the verb in the affirmative sentence, adding the particle 'not', in order to get negation. Model of a negative sentence is given in Figure 21c. According to the stated rule, negative form of the sentence from the previous example becomes ,,Strong storm did not blow off a tin roof.

Interrogative-negative sentence is formed by the use of negation of auxiliary verb in the interrogative sentence. Model of interrogative-negative sentence is given in Figure 2 Id. According to the stated rule, interrogative-negative form of the sentence from the previous example becomes ,,Didn't strong storm blow off a tin roof.

Interrogative ,,WH" question sentence is formed by placing question word before the auxiliary verb in the interrogative sentence, most often interrogative pronoun. Model of ,,WH" question sentence is given in Figure 2 Ie. According to the stated rule, interrogative sentence from the previous example is transformed into the question ,,What did strong storm blow off.

Generated sentence from module 500, NLGT, is forwarded into module 504, module TTS, where sentence text in the target (English) language is transformed into speech signal, which is presented to the user 505 in the target language. This invention anticipates the possibility of incorporation of paralinguistic information in speech synthesizer 504. The block for generation of paralinguistic information 506 uses paralinguistic information of the source language from interlingua reservoir, module 401 (Figure 19), as well as additional information from NLGT block which are specific for target language (paralinguistic information in the speech signal can be different for different languages). This invention describes the system and method for translation of communicative speech by application of interlingua resources as universal basis for multilingual translation. The invention relates to free speech communication within the dictionary of a limited volume (which actually does not represent limitation of solution, but it does represent inherent characteristic of the system) and with specific requirements (which do not limit the possibilities of the system) as regards communicative use of the system.

The solution is specific due to generalized interaction of the language via interlingua domain which contains formal descriptions, and speech and language of the source speaker in the form of concepts which are then accessible for the synthesis of other languages. The example shows the procedure of translation from Serbian language into English language. Particularly emphasized are details in the analysis of Serbian language, with the whole range of new solutions.

Methods and techniques of processing speech signals and language analysis in this invention can be implemented either like software unit, or by modules or according to modules which perform certain functions described in this invention. Program codes can be memorized in memory units and performed by processors such as PC, PDA, DSP, etc.

Details of the invention described here enable any expert in this area to implement generic principles of this invention into different languages, without leaving the scope of this invention

Claims

1. System for multilingual translation of communicative speech from one language into other languages by application of interlingua resources as a universal basis for multilingual translation, wherein it contains interlingua domain ID in which there is interlingua reservoir of concepts IRC and interlingua bank of bilingual dictionaries IBBD; interlingua domain that can be accessed by random number of languages; where each language accesses interlingua domain via access point PT; where each language has two- way analytic-synthetic language and speech processing; where each language uses automatic speech recognition ASR and conversion of the speech signal into text; where each language has speech synthesis based on text-to-speech signal TTS; where each language contains analysis of the source sentence based on grammar rules and its transformation into a set of linguistic concepts; where each language, as the target language, contains language synthesis based on transformation of the set of linguistic concepts and grammar rules of the target language.

2. System according to requirement 1, wherein it contains solution for translation from Serbian language into English language, i.e. it contains analytical processing of source Serbian language in the access to interlingua domain and synthetic generation of the target English speech from linguistic concepts in interlingua domain.

3. System according to requirement 2, wherein it contains subsystem for automatic speech recognition ASR within the volume of a given dictionary and its conversion to text with interactive relation with the speaker in the sense of correction of incorrectly pronounced word.

4. System according to requirement 2, wherein it contains subsystem for natural language understanding NLU which analyses input source (Serbian language) sentence on a lexical, syntactic and semantic level and transforms it into a set of linguistic concepts of generalized form.

5. System according to requirement 2, wherein it contains subsystem for natural (Serbian) language generation NLGs, i-e- sentence synthesis in Serbian language from linguistic concepts obtained by analytic method, which realizes feedback with the speaker (user of the system) with the aim of controlling and verifying validity of analytical procedure.

6. System according to requirement 2, wherein it contains monolingual dictionary of annotated words and monolingual phrase dictionary the content of which is in complete accordance with bilingual dictionaries.

7. System according to requirement 2, wherein it contains bank of grammar rules of Serbian language on connecting syntactic meanings of words in a sentence and the bank of models of Serbian sentences specifically structured according to the needs of multilingual translation.

8. System according to requirement 1, wherein it contains subsystem for identification of paralinguistic information in the speech signal of the source (Serbian) language and language structure of the analysed sentence.

9. System according to requirement 1, wherein it contains interlingua reservoir of linguistic concepts IRC, which stores information extracted by analysis of the source speech and language and which represent universal basis for the synthesis of different target discourses and languages, and has open structure which allows addition of linguistic concepts of a new language.

10. System according to requirement 1, wherein it contains interlingua bank of bilingual dictionaries IBBD, which includes bilingual annotated dictionaries and bilingual phrase dictionaries of each pair of languages which is connected with interlingua domain via access points, bilingual dictionaries being formed separately for each direction of the translation.

11. System according to requirement 2, wherein it contains subsystem for natural (English) language generation NLGT, as the target language, i.e. sentence synthesis in

English language based on linguistic concepts obtained from interlingua domain ID.

12. System according to requirement 2, wherein it contains bank of grammar rules of English language on connecting syntactic meanings of words in a sentence, and bank of models of English sentences structured according to natural English language.

13. System according to requirement 1, wherein it contains subsystem for generation of paralinguistic information in the speech signal of the target (English) language using paralinguistic information of the source (Serbian) language from interlingua reservoir, as well as additional information from NLG_T block, which are specific for target language.

14. The method for multilingual translation of communicative speech from one language into other languages wherein interlingua domain makes its basis as a universal basis for multilingual translation, which contains all the information obtained by analysis of source language which are necessary and sufficient for synthesis of any target language; where source speech is first transformed into text; where text of the source speech is analysed based on the grammar rules of the source language; where lexical, syntactic and semantic analyses result in language concepts as universal information based on which sentence in any language can be synthesized (generated); where synthesis (generation) of the sentence in target language is performed based on language concepts from interlingua domain along with the application of grammar rules of the target language; and where target speech is synthesized based on conversion of sentence text into speech signal.

15. The method according to requirement 14 wherein systematic mistakes in ASR module in recognition of words in different cases or verb forms, due to complex morphology of Serbian language, are statistically corrected by the formation of a list consisting of n words, ranked according to a posteriori probability, i.e. probability that exactly these words were pronounced.

16. The method according to requirement 14 wherein identification of phrases in the source sentence is performed by the complete search, according to all the possible lengths of phrases and according to all possible positions of a phrase in a source sentence.

17. The method according to requirement 14 wherein analysis of the structure of the source sentence is performed based on the model of sentences in Serbian language formed based on grammar rules and where models are structured in such a way so as to formalize forms of analysed sentences, which in most cases correspond to grammar structures of Serbian sentences, but can also be easily and correctly interpreted by other languages.

18. The method according to requirements 14 and 17 wherein restructuring of an input sentence is based on specific method based on graph theory and solution of generalized problem of traveling salesman and where graph of an input sentence consists of supernodes which are joined by words from the input sentence and subnodes which represent syntactic meanings of words.

19. The method according to requirements 17 and 18 wherein transformation of input sentence into interlingua concepts is based on grammar, syntactic and semantic rules of the source (Serbian) language through which formal description of the meaning of analysed sentence is reached.

20. The method according to requirement 14 wherein word polysemy in translation into target language is solved based on the application of grammar rules of the target language and specific method of the choice of meanings based on graph theory.

21. The method according to requirements 8 and 13 wherein paralinguistic information is identified in the source speech and language and, via interlingua domain, transferred to the side of the target language, partly modified and integrated into prosody elements of synthesized speech.