Multiset-Valued Linear Index Grammars: Imposing Dominance Constraints on Derivations

Multiset-Valued Linear Index Grammars: Imposing Dominance Constraints on Derivations Abstract This paper defines multiset-valued linear index gram- mar and unordered vector grammar with dominance links. The former models certain uses of multiset- valued feature structures in unification-based for- malisms, 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 im- portant subset is at most context-sensitive and polyno- mially 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 (un- der standard assumptions concerning the recursive na- ture 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 computa- tional linguists, in particular, polynomial parsability and restricted weak generative capacity. These mathe- matical models include tree adjoining grammar (TAG) (Joshi et al., 1975; Joshi, 1985), head grammar (Pollard, 1984), combinatory categorial grammar (CCG) (Steed- man, 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 vari- ant 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 right-hand side of a rule. In a LIG, the stack is copied to exactly one right-hand side nonterminal. 1 1Note that a LIG is not an IG that is linear (i.e., whose productions have at most one nonterminal on the right-hand Owen Rambow Univesit@ Paris 7 UFR Linguistique, TALANA Case 7003, 2, Place Jussieu F-75251 Paris Cedex 05, France rambow©linguist, j ussieu, fr While LIG-equivalent formalisms have been shown to provide adequate formal power for a wide range of lin- guistic phenomena (including the aforementioned Swiss German construction), the need for other mathemati- cal formalisms has arisen in several unrelated areas. In this paper, we discuss three such cases. First, captur- ing several semantic and syntactic issues in unification- based formalisms leads to the use of multiset-valued feature structures. Second, word order facts from lan- guages such as German, Russian, or Turkish cannot be derived by LIG-equivalent formalisms. Third, a gener- alization of trees to "quasi-trees" (Vijay-Shanker, 1992) in the spirit of D-Theory (Marcus et al., 1983) leads to the definition of a new formal system. In this pa- per, we introduce two new equivalent mathematical for- malisms which provide adequate descriptions for these three phenomena. The paper is structured as follows. First, we present the three phenomena in more detail. We then …

Content truncated to 500 words