Automatic translation has seen tremendous progress in recent years, mainly thanks to statistical methods applied to large parallel corpora. Transductions represent a principled approach to modeling translation, but existing transduction classes are either not expressive enough to capture structural regularities between natural languages or too complex to support efficient statistical induction on a large scale. A common approach is to severely prune search over a relatively unrestricted space of transduction grammars. These restrictions are often applied at different stages in a pipeline, with the obvious drawback of committing to irrevocable decisions that should not have been made. In this thesis we will instead restrict the space of transduction grammars to a space that is less expressive, but can be efficiently searched. First, the class of linear transductions is defined and characterized. They are generated by linear transduction grammars, which represent the natural bilingual case of linear grammars, as well as the natural linear case of inversion transduction grammars (and higher order syntax-directed transduction grammars). They are recognized by zipper finite-state transducers, which are equivalent to finite-state automata with four tapes. By allowing this extra dimensionality, linear transductions can represent alignments that finite-state transductions cannot, and by keeping the mechanism free of auxiliary storage, they become much more efficient than inversion transductions. Secondly, we present an algorithm for parsing with linear transduction grammars that allows pruning. The pruning scheme imposes no restrictions a priori, but guides the search to potentially interesting parts of the search space in an informed and dynamic way. Being able to parse efficiently allows learning of stochastic linear transduction grammars through expectation maximization. All the above work would be for naught if linear transductions were too poor a reflection of the actual transduction between natural languages. We test this empirically by building systems based on the alignments imposed by the learned grammars. The conclusion is that stochastic linear inversion transduction grammars learned from observed data stand up well to the state of the art.

Made available in DSpace on 2016-08-17T14:52:42Z (GMT). No. of bitstreams: 1 Nilson Santos Costa.pdf: 955701 bytes, checksum: 32b64aae5f4201f9b4db958e974f82df (MD5) Previous issue date: 2002-03-01 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / One of the difficullties when building an Intelligent Tutoring System (ITS) is the domain model definition. This must be the result of knowledge acquisition from an experts, usually a teacher. This thesis presents the definition, modelling and implementation of an authoring tool. This tool, named authoring, provides cognitive evaluations to organize a knowledge set within an intelligent tutoring system. Through this tool, the knowledge (domain) of an Expert will be available for Mathnet System. This happens due to the edition or creation of an Expert authoring into a specific domain (knowledge). By the measures, it is possible the automation of a good curricular choice to the next phase to be some proposed by the peer, simulating the teacher s experience, in order to minimize the learning process and provide the use of many pedagogical strategies. Thus, the modelling and implementation of the authoring tool acts as a mechanism of creation and test of knowledge (domain). / Uma das maiores dificuldades na construção de um Sistema Tutorial Inteligente (STI) é a construção do Modelo de Domínio. Este deve ser o resultado da aquisição de conhecimentos a partir dos especialistas, geralmente professores da área e de pedagogia. Este trabalho apresenta a definição, modelagem e implementação de uma ferramenta de autoria. Esta ferramenta, denominada de autoria, terá medidas cognitivas para ordenar um conjunto de conhecimento para um Sistema Tutor Inteligente (STI). Com esta ferramenta, será disponibilizado o conhecimento (domínio) de um especialista para o sistema Mathnet1. Isto ocorrerá mediante a edição ou criação de uma autoria do especialista em um domínio específico (conhecimento). Por meio destas medidas será possível a automação de uma boa escolha curricular para a próxima etapa a ser trabalhada com o aprendiz (aluno), simulando a experiência do professor, a fim de minimizar o tempo de aprendizado e possibilitar a utilização de diversas estratégias pedagógicas. Desta maneira, a modelagem e implementação da ferramenta de autoria servirão como mecanismo de criação e testes de conhecimento (domínio).

The field of statistical machine translation has made tremendous progress due to the rise of statistical methods, making it possible to obtain a translation system automatically from a bilingual collection of text. Some approaches do not even need any kind of linguistic annotation, and can infer translation rules from raw, unannotated data. However, most state-of-the art systems do linguistic structure little justice, and moreover many approaches that have been put forward use ad-hoc formalisms and algorithms. This inevitably leads to duplication of effort, and a separation between theoretical researchers and practitioners. In order to remedy the lack of motivation and rigor, the contributions of this dissertation are threefold: 1. After laying out the historical background and context, as well as the mathematical and linguistic foundations, a rigorous algebraic model of machine translation is put forward. We use regular tree grammars and bimorphisms as the backbone, introducing a modular architecture that allows different input and output formalisms. 2. The challenges of implementing this bimorphism-based model in a machine translation toolkit are then described, explaining in detail the algorithms used for the core components. 3. Finally, experiments where the toolkit is applied on real-world data and used for diagnostic purposes are described. We discuss how we use exact decoding to reason about search errors and model errors in a popular machine translation toolkit, and we compare output formalisms of different generative capacity.

The specification of a decoder, i.e., a program that translates sentences from one natural language into another, is an intricate process, driven by the application and lacking a canonical methodology. The practical nature of decoder development inhibits the transfer of knowledge between theory and application, which is unfortunate because many contemporary decoders are in fact related to formal-language theory. This thesis proposes an algebraic framework where a decoder is specified by an expression built from a fixed set of operations. As yet, this framework accommodates contemporary syntax-based decoders, it spans two levels of abstraction, and, primarily, it encourages mutual stimulation between the theory of weighted tree automata and the application.

La complexité des systèmes conçus actuellement devient de plus en plus importante. En effet,afin de rester compétitives, les entreprises concevant des systèmes cherchent à leur rajouter de plus en plusde fonctionnalités. Cette compétitivité introduit aussi une demande de réactivité lors de la conception desystèmes, pour que le système puisse évoluer lors de sa conception et suivre les demandes du marché.Un des éléments identifiés comme empêchant ou diminuant cette capacité à concevoir de manière flexibledes systèmes complexes concerne les spécifications des systèmes, et en particulier l’utilisation de la languenaturelle pour spécifier les systèmes. Tout d’abord, la langue naturelle est intrinsèquement ambiguë et celarisque donc de créer des non-conformités si client et fournisseur d’un système ne sont pas d’accord sur lesens de sa spécification. De plus, la langue naturelle est difficile à traiter automatiquement, par exemple, onpeut difficilement déterminer avec un programme informatique que deux exigences en langue naturelle secontredisent. Cependant, la langue naturelle reste indispensable dans les spécifications que nous étudions,car elle reste un moyen de communication pratique et très répandu.Nous cherchons à compléter ces exigences en langue naturelle avec des éléments permettant à la fois de lesrendre moins ambiguës et de faciliter les traitements automatiques. Ces éléments peuvent faire partie demodèles (d’architecture par exemple) et permettent de définir le lexique et la syntaxe utilisés dans lesexigences. Nous avons testé les principes proposés sur des spécifications industrielles réelles et développéun prototype logiciel permettant de réaliser des tests sur une spécification dotée de ces éléments de syntaxeet de lexique. / Systems are becoming more and more complex, because to stay competitive, companies whichdesign systems search to add more and more functionalities to them. Additionally, this competition impliesthat the design of systems needs to be reactive, so that the system is able to evolve during its conception andfollow the needs of the market.This capacity to design flexibly complex systems is hindered or even prevented by various variouselements, with one of them being the system specifications. In particular, the use of natural language tospecify systems have several drawbacks. First, natural language is inherently ambiguous and this can leadsto non-conformity if customer and supplier of a system disagree on the meaning of its specification.Additionally, natural language is hard to process automatically : for example, it is hard to determine, usingonly a computer program, that two natural language requirements contradict each other. However, naturallanguage is currently unavoidable in the specifications we studied, because it remains very practical, and itis the most common way to communicate.We aim to complete these natural language requirements with elements which allow to make them lessambiguous and facilitate automatic processing. These elements can be parts of models (architectural modelsfor example) and allow to define the vocabulary and the syntax of the requirements. We experimented theproposed principles on real industrial specifications and we developped a software prototype allowing totest a specification enhanced with these vocabulary and syntax elements.

This work deals with syntax analysis problems based on multi-generation. The basic idea is to create computer program, which transforms one input string to n -1 output strings. An Input of this program is some plain text file created by user, which contains n grammar rules. Just one grammar from the input file is marked as an input grammar and others n -1 grammars are output grammars. This program creates list of used input grammar rules for an input string and uses corresponding output grammar rules for the creation of n -1 output strings. The program is written in C++ and Bison

In this doctoral dissertation, we studied and solved several questions regarding positional and abstract numeration systems. Each particular problem is the focus of a chapter. The first problem concerns the study of the preservation of recognizability under multiplication by a constant in abstract numeration systems built on polynomial regular languages. We obtained several results generalizing those from P. Lecomte and M. Rigo. The second problem we considered is a decidability problem, which was already studied, most notably, by J. Honkala and A. Muchnik. For our part, we studied this problem for two new cases: the linear positional numeration systems and the abstract numeration systems. Next, we focused on the extension to the multidimensional setting of a result of A. Maes and M.~Rigo regarding S-automatic infinite words. We obtained a characterization of multidimensional S-automatic words in terms of multidimensional (non-necessarily uniform) morphisms. This result can be viewed as the analogous of O. Salon's extension of a theorem of A. Cobham. Finally, generalizing results of P. Lecomte and M. Rigo, we proposed a formalism to represent real numbers in the general framework of abstract numeration systems built on languages that are not necessarily regular. This formalism encompasses in particular the rational base numeration systems, which have been recently introduced by S. Akiyama, Ch. Frougny, and J. Sakarovitch. Finally, we ended with a list of open questions in the continuation of this work./Dans cette dissertation, nous étudions et résolvons plusieurs questions autour des systèmes de numération abstraits. Chaque problème étudié fait l'objet d'un chapitre. Le premier concerne l'étude de la conservation de la reconnaissabilité par la multiplication par une constante dans des systèmes de numération abstraits construits sur des langages réguliers polynomiaux. Nous avons obtenus plusieurs résultats intéressants généralisant ceux de P. Lecomte et M. Rigo. Le deuxième problème auquel je me suis intéressée est un problème de décidabilité déjà étudié notamment par J. Honkala et A. Muchnik et ici décliné en deux nouvelles versions : les systèmes de numération de position linéaires et les systèmes de numération abstraits. Ensuite, nous nous penchons sur l'extension au cas multidimensionnel d'un résultat d'A. Maes et de M. Rigo à propos des mots infinis S-automatiques. Nous avons obtenu une caractérisation des mots S-automatiques multidimensionnels en termes de morphismes multidimensionnels (non nécessairement uniformes). Ce résultat peut être vu comme un analogue de l'extension obtenue par O. Salon d'un théorème de A. Cobham. Finalement, nous proposons un formalisme de la représentation des nombres réels dans le cadre général des systèmes de numération abstraits basés sur des langages qui ne sont pas nécessairement réguliers. Ce formalisme englobe notamment le cas des numérations en bases rationnelles introduits récemment par S. Akiyama, Ch. Frougny et J. Sakarovitch. Nous terminons par une liste de questions ouvertes dans la continuité de ce travail.

Nous nous positionnons dans un contexte d'informatique ambiante dans lequel il arrive que les besoins de l'utilisateur n'aient pas été prévus, notamment en situation exceptionnelle. Dans ce cas, il peut ne pas exister de système préconçu qui réponde exactement à ces besoins. Pour les satisfaire, il faut alors pouvoir composer les systèmes disponibles dans l'environnement, et le système composé doit permettre à l'utilisateur de faire des choix à l'exécution. Ainsi, l'utilisateur a la possibilité d'adapter l'exécution de la composition à son contexte. Cela signifie que la composition intègre des structures de contrôle de l'exécution, destinées à l'utilisateur : la composition est dite flexible. Dans cette thèse, nous proposons de répondre au problème de la composition flexible en contexte d'intelligence ambiante avec un planificateur produisant des plans flexibles. Dans un premier temps, nous proposons une modélisation de la planification flexible. Pour cela, nous définissons les opérateurs de séquence et d'alternative, utilisés pour caractériser les plans flexibles. Nous définissons deux autres opérateurs au moyen de la séquence et de l'alternative : l'entrelacement et l'itération. Nous nous référons à ce cadre théorique pour délimiter la flexibilité traitée par notre planificateur Lambda-Graphplan. L'originalité de Lambda-Graphplan est de produire des itérations en s'appuyant sur une approche par graphe de planification. Nous montrons notamment que Lambda-Graphplan est très performant avec les domaines se prêtant à la construction de structures itératives. / In a context of Ambient Intelligence, some of the user's needs might not be anticipated, e.g. when the user is in an unforeseen situation. In this case, there could exist no system that exactly meets their needs. By composing the available systems, the user could obtain a new system that satisfies their needs. In order to adapt the composition to the context, the composition must allow the user to make choices at runtime. So the composition includes control structures for the user: the composition is flexible. In this thesis, I deal with the problem of the flexible composition by automated planning. I propose a model of flexible planning. The sequence and the choice operators are defined and used to characterize flexible plans. Then, two other operators are derived from the sequence and the choice operators: the interleaving and the iteration operators. I refer to this framework to define the flexibility produced by my planner, Lambda-Graphplan, which is based on the planning graph. The originality of Lambda-Graphplan is to produce iterations. I show that Lambda-Graphplan is very efficient on domains that allow the construction of iterative structures.

Made available in DSpace on 2016-08-17T14:53:19Z (GMT). No. of bitstreams: 1 dissertacao Carlos Cesar.pdf: 5267302 bytes, checksum: 26bac06a2f7777c938fb717c801f59cd (MD5) Previous issue date: 2011-07-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / In this thesis, an approach based on Set Theory and on the Z Formal Language Specification is presented to formalize the transformations between models in the context of Model Driven Engineering (MDE). The motivation for this research is justified due the ambiguities and inconsistencies present in the models of transformation used to abstract the model transformation process in the MDE context. The precision absence in these the models lead the user to misinterpret complex structures present in the mapping of the source model elements to the target model elements. In this context, we proposed to develop a formal methodology that eliminates the ambiguities and inconsistencies present in the informal representations of model transformation in MDE. To solve this problem, a Formal and Conceptual Framework is developed that groups the elements involved in the process of transformation, represented by mathematical artifacts from the Set Theory and specified on Z language. This Framework is validated through a case study that contains complex transformations, tested on the mathematical proof tool Z/EVES, which supports statements made in Z language. / Nesta dissertação, apresenta-se uma abordagem baseada na Teoria dos Conjuntos e na Linguagem de Especificação Formal Z para formalizar a Transformação entre Modelos dentro do contexto da Engenharia Dirigida a Modelos (MDE). A motivação desta pesquisa se deu devido a constatação de que a literatura sobre MDE tem apresentado ambiguidades e inconsistências nos modelos utilizados para abstrair o processo de transformação de modelos no contexto da MDE. Esta falta de precisão nestes tipos de modelos leva o usuário a interpretar de forma errada estruturas complexas presentes no mapeamento de elementos do modelo fonte para o modelo alvo. Sendo assim, propõe-se desenvolver uma metodologia formal que elimine as ambiguidades e inconsistências presentes nas representações informais da transformação de modelos da MDE. Para solucionar este problema, desenvolveu-se um Framework Conceitual Formal que agrupa os elementos envolvidos no processo de transformação, onde estes são representados através de artefatos matemáticos da Teoria dos Conjuntos e especificados em linguagem Z. Este Framework é validado através de um estudo de caso que contêm transformações, testadas na ferramenta de prova matemática Z/EVES, que suporta declarações feitas em linguagem Z.

Tato disertační práce zavádí jednostranné gramatiky s nahodilým kontextem jako řízené gramatiky založené na bezkontextových gramatikách. V těchto gramatikách je ke každému pravidlu přiřazena množina povolujících symbolů a množina zakazujících symbolů a množina pravidel je rozdělena na množinu levých pravidel s nahodilým kontextem a množinu pravých pravidel s nahodilým kontextem . Levým pravidlem s nahodilým kontextem lze přepsat neterminál pokud se všechny povolující symboly vyskytují vlevo od přepisovaného neterminálu a žádný zakazující symbol tam přítomen není. Pravé pravidlo s nahodilým kontextem lze aplikovat analogicky, ale ona kontrola na přítomnost a nepřítomnost symbolů je provedena doprava od přepisovaného neterminálu. Práce je rozdělena na tři části. První část uvádí motivaci za zavedením jednostranných gramatik s nahodilým kontextem a umisťuje materiál pokrytý v této práci do vědeckého kontextu. Poté dává přehled základů teorie formálních jazyků a některých méně známých oblastí, jejichž znalost je nutná pro pochopení studovaného tématu. Druhá část tvoří jádro práce. Formálně definuje jednostranné gramatiky s nahodilým kontextem a studuje je z mnoha pohledů. Mezi studovaná témata patří generativní síla, vztah k jiným typům gramatik, redukce, normální formy, nejlevější derivace, zobecněné a LL verze těchto gramatiky. Třetí část této práce zakončuje diskusi několika poznámkami. Mezi ně patří poznámky týkající se aplikovatelnosti zavedených gramatik v praxi, bibliografie a otevřených problémů.