O_n is an n-MCFL

Commutative properties in formal languages pose problems at the frontier of computer science, computational linguistics and computational group theory. A prominent problem of this kind is the position of the language O_n, the language that contains the same number of letters a_i and a¯_i with 1⩽i⩽n, in the known classes of formal languages. It has recently been shown that O_n is a Multiple Context-Free Language (MCFL). However the more precise conjecture of Nederhof that O_n is an MCFL of dimension n was left open. We prove this conjecture using tools from algebraic topology. On our way, we prove a variant of the necklace splitting theorem.