Left-right trees, a new tree structure for machine translation

✍ Scribed by Kouichi Kurokawa; Takumi Kasai

• Publisher: John Wiley and Sons
• Year: 1998
• Tongue: English
• Weight: 214 KB
• Volume: 29
• Category: Article
• ISSN: 0882-1666
• DOI: 10.1002/(sici)1520-684x(199805)29:5<84::aid-scj9>3.0.co;2-j

✦ Synopsis

This paper describes a new tree structure called the left-right tree, along with its grammar and automaton, which form the theoretical basis for an English-Japanese machine translator developed by the authors. A left-right tree is a tree that differentiates between left children and right children. An English sentence is transformed into a set of left-right trees by labeling each node of the left-right tree with an English word. To represent a language, which is a collection of such left-right trees, we define a grammar for left-right tree languages, called the tree categorical grammar. We also define the valenced pushdown transducer as a formalized model of the parser used in the translator. Due to the valence property of the symbols, the work of the stack is restricted in the pushdown transducer. We demonstrate the equivalence of the classes of left-right tree languages produced by different representations and explain some of the properties satisfied by the classes.