Résumé | There are some natural languages that allow the free ordering of words or phrases in their sentences while preserving grammaticality. In order to model such sentences, we consider a term algebra with two operators: one that models the usual concatenation, and another that denotes the "free order combination", that is the concatenation of its arguments in any possible left-to-right order.
Multiple Context-Free Grammars (MCFG) are an extension of context-free grammars, where non-terminals in a derivation are associated with a tuple of strings (rather than a single string). Each production rule then specifies how the strings on the right-hand side are combined to form the strings of the left-hand side.
We consider an extension of MCFG that, instead of strings, produces terms (or contexts) over the previously described algebra, to represent sentences with free order. We describe several natural subclasses of those so-called commutative grammars, and give an account of the computational complexity associated with their (universal) parsing problems.
This is joint work with Sylvain Salvati. |