Generalized Multitext Grammars

Generalized Multitext Grammars I. Dan Melamed Computer Science Department New York University 715 Broadway, 7th Floor New York, NY, 10003, USA � lastname � @cs.nyu.edu Giorgio Satta Dept. of Information Eng’g University of Padua via Gradenigo 6/A I-35131 Padova, Italy � lastname � @dei.unipd.it Benjamin Wellington Computer Science Department New York University 715 Broadway, 7th Floor New York, NY, 10003, USA � lastname � @cs.nyu.edu Abstract Generalized Multitext Grammar (GMTG) is a syn- chronous grammar formalism that is weakly equiv- alent to Linear Context-Free Rewriting Systems (LCFRS), but retains much of the notational and in- tuitive simplicity of Context-Free Grammar (CFG). GMTG allows both synchronous and independent rewriting. Such flexibility facilitates more perspic- uous modeling of parallel text than what is possible with other synchronous formalisms. This paper in- vestigates the generative capacity of GMTG, proves that each component grammar of a GMTG retains its generative power, and proposes a generalization of Chomsky Normal Form, which is necessary for synchronous CKY-style parsing. 1 Introduction Synchronous grammars have been proposed for the formal description of parallel texts representing translations of the same document. As shown by Melamed (2003), a plausible model of parallel text must be able to express discontinuous constituents. Since linguistic expressions can vanish in transla- tion, a good model must be able to express inde- pendent (in addition to synchronous) rewriting. In- version Transduction Grammar (ITG) (Wu, 1997) and Syntax-Directed Translation Schema (SDTS) (Aho and Ullman, 1969) lack both of these prop- erties. Synchronous Tree Adjoining Grammar (STAG) (Shieber, 1994) lacks the latter and allows only limited discontinuities in each tree. Generalized Multitext Grammar (GMTG) offers a way to synchronize Mildly Context-Sensitive Grammar (MCSG), while satisfying both of the above criteria. The move to MCSG is motivated by our desire to more perspicuously account for certain syntactic phenomena that cannot be easily captured by context-free grammars, such as clitic climbing, extraposition, and other types of long- distance movement (Becker et al., 1991). On the other hand, MCSG still observes some restrictions that make the set of languages it generates less ex- pensive to analyze than the languages generated by (properly) context-sensitive formalisms. More technically, our proposal starts from Mul- titext Grammar (MTG), a formalism for synchro- nizing context-free grammars recently proposed by Melamed (2003). In MTG, synchronous rewriting is implemented by means of an indexing relation that is maintained over occurrences of nonterminals in a sentential form, using essentially the same ma- chinery as SDTS. Unlike SDTS, MTG can extend the dimensionality of the translation relation be- yond two, and it can implement independent rewrit- ing by means of partial deletion of syntactic struc- tures. Our proposal generalizes MTG by moving from component grammars that generate context- free languages to component grammars whose gen- erative power is equivalent to Linear Context-Free Rewriting Systems (LCFRS), a formalism for de- scribing a class of MCSGs. The generalization is achieved by allowing context-free productions to rewrite tuples of strings, rather than single strings. Thus, we retain the intuitive top-down definition of …

Content truncated to 500 words