tailieunhanh - Báo cáo khoa học: "Generalized Multitext Grammars"

Generalized Multitext Grammar (GMTG) is a synchronous grammar formalism that is weakly equivalent to Linear Context-Free Rewriting Systems (LCFRS), but retains much of the notational and intuitive simplicity of Context-Free Grammar (CFG). GMTG allows both synchronous and independent rewriting. Such flexibility facilitates more perspicuous modeling of parallel text than what is possible with other synchronous formalisms. This paper investigates 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. . | Generalized Multitext Grammars I. Dan Melamed Computer Science Department New York University 715 Broadway 7th FlOor New York NY 1o003 USA lastname @ Giorgio Satta Dept. of Information Eng g University of Padua via Gradenigo 6 A I-35131 Padova Italy lastname @ Benjamin Wellington Computer Science Department New York University 715 Broadway 7th Floor New York NY 1o003 USA lastname @ Abstract Generalized Multitext Grammar GMTG is a synchronous grammar formalism that is weakly equivalent to Linear Context-Free Rewriting Systems LCFRS but retains much of the notational and intuitive simplicity of Context-Free Grammar CFG . GMTG allows both synchronous and independent rewriting. Such flexibility facilitates more perspicuous modeling of parallel text than what is possible with other synchronous formalisms. This paper investigates 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 translation a good model must be able to express independent in addition to synchronous rewriting. Inversion Transduction Grammar ITG Wu 1997 and Syntax-Directed Translation Schema SDTS Aho and Ullman 1969 lack both of these properties. 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 .