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.
