On is an n-MCFL

Sylvain Salvati (1, 2, 3)

1 Université de Lille
2 LINKS - Linking Dynamic Data
3 CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189

The language O n is the language built on the alphabet Σ n = {a i , b i | i ∈ [1, n]} and that contains exactly all those words w which, for every i in [1, n], have the same number of occurrences of a i and of b i. If we write |w| c the number of occurrences of the letter c in w, then this condition becomes that for every i in [1, n], |w| ai = |w| bi. It has first been conjectured that the language O 2 was not a Multiple Context Free Language (MCFL), but it was subsequently shown that it actually was an MCFL [Sal15] and more precisely an MCFL of dimension 2 (a 2-MCFL) while not being a well-nested MCFL of dimension 2 [KS12] (a 2-MCFL wn). Giving a similar proof of the same result, Nederhof [Ned16] conjectured that O n is an n-MCFL. As pointed in [Ned16], a simple pumping argument shows taht for every m < n, O n cannot be an MCFL of dimension m. A recent breakthrough has been made about that conjecture by Meng-Che Ho [Hoar] who proved that O n is an MCFL for every n. However the dimension of the MCFL induced by the proof is larger than n, it is 8 n+1 2 − 2. All the proofs related to these results are based on algebraic topology. While the result of [Sal15] as well as the proof of [Ned16] strongly use some properties of the plane (the existence of winding numbers of curves around points), the proof of [Hoar] is based on a more general and well-known result of algebraic topol-ogy: Borsuk-Ulam Theorem. This theorem has topological proofs, but it can also be seen as a consequence of a combinatorial lemma of Tucker [Tuc45]. In this paper, we present a rather elementary proof that O n is an n-MCFL using octahedral Tucker's Lemma. Interestingly several theorems that were proved using Borsuk-Ulan Theorem have been reproved using the octohedral Tucker's Lemma. For example Matoušek[Mat04] gave a combinatorial proof of Kneser Theorem proving and using that lemma. Similarly P` alvölgyi [Pál09] used that lemma so as to give a combinatorial proof of the bound for the splitting necklace problem. Interestingly the first bounds for this problem were proved using Borsuk-Ulam theorem with the very same technique as the one used in [Hoar] so as to prove that O n is an MCFL.

Domaines: Informatique et langage [cs.CL]; Topologie algébrique [math.AT]; Combinatoire [math.CO]; Théorie des groupes [math.GR]

Sylvain Salvati. On is an n-MCFL. [Research Report] Université de Lille, INRIA, CRIStAL CNRS. 2018. ⟨hal-01771670v1⟩