Synchronous Models of Language

Synchronous Models of Language Owen Rambow CoGenTex, Inc. 840 Hanshaw Road, Suite 11 Ithaca, NY 14850-1589 owen@cogentex, com Giorgio Satta Dipartimento di Elettronica ed Informatica Universit~ di Padova via Gradenigo, 6/A 1-35131 Padova, Italy satta@dei, unipd, it Abstract In synchronous rewriting, the productions of two rewriting systems are paired and applied synchronously in the derivation of a pair of strings. We present a new syn- chronous rewriting system and argue that it can handle certain phenomena that are not covered by existing synchronous sys- tems. We also prove some interesting for- mal/computational properties of our sys- tem. 1 Introduction Much of theoretical linguistics can be formulated in a very natural manner as stating correspondences (translations) between layers of representation; for example, related interface layers LF and PF in GB and Minimalism (Chomsky, 1993), semantic and syntactic information in HPSG (Pollard and Sag, 1994), or the different structures such as c-structure and f-structure in LFG (Bresnan and Kaplan, 1982). Similarly, many problems in natural language pro- cessing, in particular parsing and generation, can be expressed as transductions, which are calculations of such correspondences. There is therefore a great need for formal models of corresponding levels of representation, and for corresponding algorithms for transduction. Several different transduction systems have been used in the past by the computational and theoret- ical linguistics communities. These systems have been borrowed from translation theory, a subfield of formal language theory, or have been originally (and sometimes redundantly) developed. Finite state transducers (for an overview, see, e.g., (Aho and Ullman, 1972)) provide translations between regular languages. These devices have been pop- ular in computational morphology and computa- tional phonology since the early eighties (Kosken- niemi, 1983; Kaplan and Kay, 1994), and more re- cently in parsing as well (see, e.g., (Gross, 1989; Pereira, 1991; Roche, 1993)). Pushdown transduc- ers and syntax directed translation schemata (SDTS) (Aho and Ullman, 1969) translate between context- free languages and are therefore more powerful than finite state transducers. Pushdown transducers are a standard model for parsing, and have also been used (usually implicitly) in speech understanding. Recently, variants of SDTS have been proposed as models for simultaneously bracketing parallel cor- pora (Wu, 1995). Synchronization of tree adjoin- ing grammars (TAGs) (Shieber and Schabes, 1990; Shieber, 1994) are even more powerful than the pre- vious formalisms, and have been applied in machine translation (Abeill6, Schabes, and Joshi, 1990; Egedi and Palmer, 1994; Harbusch and Poller, 1994; Pri- gent, 1994), natural language generation (Shieber and Schabes, 1991), and theoretical syntax (Abeilld, 1994). The common underlying idea in all of these formalisms is to combine two generative devices through a pairing of their productions (or, in the case of the corresponding automata, of their tran- sitions) in such a way that right-hand side nonter- minal symbols in the paired productions are linked. The processes of derivation proceed synchronously in the two devices by applying the paired grammar rules only to linked nonterminals introduced previ- ously in the derivation. The fact that the above sys- tems …

Content truncated to 500 words