A short proof that O_2 is an MCFL

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1117–1126, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics A short proof that O2 is an MCFL Mark-Jan Nederhof School of Computer Science University of St Andrews, UK Abstract We present a new proof that O2 is a mul- tiple context-free language. It contrasts with a recent proof by Salvati (2015) in its avoidance of concepts that seem specific to two-dimensional geometry, such as the complex exponential function. Our simple proof creates realistic prospects of widen- ing the results to higher dimensions. This finding is of central importance to the rela- tion between extreme free word order and classes of grammars used to describe the syntax of natural language. 1 Introduction The alphabet of the MIX language has three sym- bols, a, b and c. A string is in the language if and only if the number of a’s, the number of b’s, and the number of c’s are all the same. A different way of defining the MIX language is as permu- tation closure of the regular language (abc)∗, as noted by Bach (1981); see also Pullum (1983). If a, b and c represent, say, a transitive verb and its subject and its object, then a string in MIX represents a sentence with any number of triples of these constituents, in a hypothetical lan- guage with extreme free word order. This is ad- mittedly rather unlike any actual natural language. Joshi (1985) argued that because of this, grammat- ical formalisms for describing natural languages should not be capable of generating MIX. He also conjectured that MIX was beyond the generative capacity of one particular formalism, namely the tree adjoining grammars. Several decades passed before Kanazawa and Salvati (2012) finally proved this conjecture. MIX has been studied in the context of several other formalisms. Joshi et al. (1991) showed that MIX is generated by a generalization of tree ad- joining grammars that decouples local domination for linear precedence. Boullier (1999) showed that MIX is generated by a range concatenation gram- mar. Negative results were addressed by Sorokin (2014) for well-nested multiple context-free gram- mars, and by Capelletti and Tamburini (2009) for a class of categorial grammars. The MIX language is also of interest outside of computational linguis- tics, e.g. in computational group theory (Gilman, 2005). A considerable advance in the understanding of the MIX language is due to Salvati (2015), who showed that MIX is generated by a multiple context-free grammar (MCFG). The main part of the proof shows that the language O2 is generated by a MCFG. This language has four symbols, a, a, b and b. A string is in the language if and only if the number of a’s equals the number of a’s, and the number of b’s equals the number of b’s. MIX and O2 are rationally equivalent, which means that if one is generated by a multiple context-free gram- mar, then so is the other. The proof by Salvati …

Content truncated to 500 words