# A short proof that O2 is an MCFL

arXiv: https://arxiv.org/abs/1603.03610 · HTML: https://mlsanity.com/paper/1603.03610/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2016.

## Built on by (most cited first, 2 of 2)

- [O2 is a multiple context-free grammar: an implementation-, formalisation-friendly proof](https://mlsanity.com/paper/2405.09396/) (2024)
- [A strengthening of the MCFL-ness of O2](https://mlsanity.com/paper/2608.18813/) (2026)

## Abstract (arXiv)

We present a new proof that O2 is a multiple 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 widening the results to higher dimensions. This finding is of central importance to the relation between extreme free word order and classes of grammars used to describe the syntax of natural language.