Syntax-directed translations, tree transformations and bimorphisms

Abstract

La traducció basada en la sintaxi va sorgir en l'àmbit de la traducció automàtica dels llenguatges naturals. Els sistemes han de modelar les transformacions d'arbres, reordenar parts d'oracions, ser simètrics i posseir propietats com la componibilitat o simetria. Existeixen diverses maneres de definir transformacions d'arbres: gramàtiques síncrones, transductors d'arbres i bimorfismes d'arbres. Les gramàtiques síncrones fan tot tipus de rotacions, però les propietats matemàtiques són més difícils de provar. Els transductors d'arbres són operacionals i fàcils d'implementar, però les classes principals no són tancades sota la composició. Els bimorfismes d'arbres són difícils d'implementar, però proporcionen una eina natural per provar componibilitat o simetria. Per millorar el procés de traducció, les gramàtiques síncrones es relacionen amb els bimorfismes d'arbres i amb els transductors d'arbres. En aquesta tesi es duu a terme un ampli estudi de la teoria i les propietats dels sistemes de traducció dirigides per la sintaxi, des d'aquestes tres perspectives molt diferents que es complementen perfectament entre si: com a dispositius generatius (gramàtiques síncrones), com a màquines acceptadores (transductors) i com a estructures algebraiques (bimorfismes). S'investiguen i comparen al nivell de la transformació d'arbres i com a dispositius que defineixen translacions. L'estudi es centra en bimorfismes, amb especial èmfasi en les seves aplicacions per al processament del llenguatge natural. També es proposa una completa i actualitzada visió general sobre les classes de transformacions d'arbres definits per bimorfismes, vinculant-los amb els tipus coneguts de gramàtiques síncrones i transductors d'arbres. Provem o recordem totes les propietats interessants que les esmentades classes posseeixen, millorant així els coneixements matemàtics previs. A més, s'exposen les relacions d'inclusió entre les principals classes de bimorfismes mitjançant un diagrama Hasse, com a dispositius de traducció i com a mecanismes de transformació d'arbres.

La traducción basada en la sintaxis surgió en el ámbito de la traducción automática de los lenguajes naturales. Los sistemas deben modelar las transformaciones de árboles, reordenar partes de oraciones, ser simétricos y poseer propiedades como la composición o simetría. Existen varias maneras de definir transformaciones de árboles: gramáticas síncronas, transductores de árboles y bimorfismos de árboles. Las gramáticas síncronas hacen todo tipo de rotaciones, pero las propiedades matemáticas son más difíciles de probar. Los transductores de árboles son operacionales y fáciles de implementar pero las clases principales no son cerradas bajo la composición. Los bimorfismos de árboles son difíciles de implementar, pero proporcionan una herramienta natural para probar composición o simetría. Para mejorar el proceso de traducción, las gramáticas síncronas se relacionan con los bimorfismos de árboles y con los transductores de árboles. En esta tesis se lleva a cabo un amplio estudio de la teoría y las propiedades de los sistemas de traducción dirigidas por la sintaxis, desde estas tres perspectivas muy diferentes que se complementan perfectamente entre sí: como dispositivos generativos (gramáticas síncronas), como máquinas aceptadores (transductores) y como estructuras algebraicas (bimorfismos). Se investigan y comparan al nivel de la transformación de árboles y como dispositivos que definen translaciones. El estudio se centra en bimorfismos, con especial énfasis en sus aplicaciones para el procesamiento del lenguaje natural. También se propone una completa y actualizada visión general sobre las clases de transformaciones de árboles definidos por bimorfismos, vinculándolos con los tipos conocidos de gramáticas síncronas y transductores de árboles. Probamos o recordamos todas las propiedades interesantes que tales clases poseen, mejorando así los previos conocimientos matemáticos. Además, se exponen las relaciones de inclusión entre las principales clases de bimorfismos a través de un diagrama Hasse, como dispositivos de traducción y como mecanismos de transformación de árboles.

Syntax-based machine translation was established by the demanding need of systems used in practical translations between natural languages. Such systems should, among others, model tree transformations, re-order parts of sentences, be symmetric and possess composability or forward and backward application. There are several formal ways to define tree transformations: synchronous grammars, tree transducers and tree bimorphisms. The synchronous grammars do all kind of rotations, but mathematical properties are harder to prove. The tree transducers are operational and easy to implement, but closure under composition does not hold for the main types. The tree bimorphisms are difficult to implement, but they provide a natural tool for proving composability or symmetry. To improve the translation process, synchronous grammars were related to tree bimorphisms and tree transducers. Following this lead, we give a comprehensive study of the theory and properties of syntax-directed translation systems seen from these three very different perspectives that perfectly complement each other: as generating devices (synchronous grammars), as acceptors (transducer machines) and as algebraic structures (bimorphisms). They are investigated and compared both as tree transformation and translation defining devices. The focus is on bimorphisms as they only recently got again into the spotlight especially given their applications to natural language processing. Moreover, we propose a complete and up-to-date overview on tree transformations classes defined by bimorphisms, linking them with well-known types of synchronous grammars and tree transducers. We prove or recall all the interesting properties such classes possess improving thus the mathematical knowledge on synchronous grammars and/or tree transducers. Also, inclusion relations between the main classes of bimorphisms both as translation devices and as tree transformation mechanisms are given for the first time through a Hasse diagram. Directions for future work are suggested by exhibiting how to extend previous results to more general classes of bimorphisms and synchronous grammars.