Paper: Multiset-Valued Linear Index Grammars: Imposing Dominance Constraints On Derivations

ACL ID P94-1036
Title Multiset-Valued Linear Index Grammars: Imposing Dominance Constraints On Derivations
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1994
Authors

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.