tailieunhanh - Báo cáo khoa học: "Multiset-Valued Linear Index Grammars: Imposing Dominance Constraints on Derivations"

This paper defines multiset-valued linear index grammar and unordered vector grammar with dominance links. The former models certain uses of multisetvalued feature structures in unification-based formalisms, while the latter is motivated by word order variation and by "quasi-trees", a generalization of trees. The two formalisms are weakly equivalent, and an important subset is at most context-sensitive and polynomially parsable. Introduction Early attempts to use context-free grammars (CFGs) as a mathematical model for natural language syntax have largely been abandoned; it has been shown that (under standard assumptions concerning the recursive nature of clausal embedding) the cross-serial dependencies found in. | Multiset-Valued Linear Index Grammars Imposing Dominance Constraints on Derivations Owen Rambow Univesité Paris 7 UFR Linguistique TALANA Case 7003 2 Place Jussieu F-75251 Paris Cedex 05 France Abstract This paper defines multiset-valued linear index grammar and unordered vector grammar with dominance links. The former models certain uses of multisetvalued feature structures in unification-based formalisms while the latter is motivated by word order variation and by quasi-trees a generalization of trees. The two formalisms are weakly equivalent and an important subset is at most context-sensitive and polynomially parsable. Introduction Early attempts to use context-free grammars CFGs as a mathematical model for natural language syntax have largely been abandoned it has been shown that under standard assumptions concerning the recursive nature of clausal embedding the cross-serial dependencies found in Swiss German cannot be generated by a CFG Shieber 1985 . Several mathematical models have been proposed which extend the formal power of CFGs while still maintaining the formal properties that make CFGs attractive formalisms for formal and computational linguists in particular polynomial parsability and restricted weak generative capacity. These mathematical models include tree adjoining grammar TAG Joshi et al. 1975 Joshi 1985 head grammar Pollard 1984 combinatory categorial grammar CCG Steedman 1985 and linear index grammar LIG Gaz-dar 1988 . These formalisms have been shown to be weakly equivalent to each other Vijay-Shanker et al. 1987 Vijay-Shanker and Weir 1994 we will refer to them as LIG-equivalent formalisms . LIG is a variant of index grammar IG Aho 1968 . Like CFG IG is a context-free string rewriting system except that the nonterminal symbols in a CFG are augmented with stacks of index symbols. The rewrite rules push or pop indices from the index stack. In an IG the index stack is copied to all nonterminal symbols on the .