Language mix problem shown not to fit common grammar class
On the Kanazawa--Salvati Conjecture
Formal Languages and Automata Theory
Summary
The paper studies a language where words have equal numbers of certain letters, which is related to math structures called groups. The authors focus on a big open question about whether this language can be generated by a certain type of grammar known for nesting structure well. They translate this hard question into a simpler problem about combining words. While the main question remains unsolved, they prove that a more complex version involving four letters cannot be captured by these grammars. This builds on previous work about simpler cases with fewer letters.
What this means in practice
- •For formal language engineers: Avoid using well-nested multiple context-free grammars for certain balanced letter languages when modeling or parsing formal languages related to algebraic structures.
- •For computer algebra system developers: Refine algorithms for word problems in algebra by understanding limitations of grammar classes dealing with structured languages over groups.
A theory result. No direct application yet.
Authors
Takao Yuyama
Abstract
The language $\mathrm{MIX}$ consists of all words over a three-letter alphabet that have an equal number of occurrences of each letter. It is also the word problem of $\mathbb{Z}^2$ with respect to a suitable choice of generators. The Kanazawa--Salvati conjecture states that $\mathrm{MIX}$ is not a well-nested multiple context-free language. Every well-nested multiple context-free language is an indexed language. We reduce the conjecture to an explicit combinatorial problem about tuples of words, which is easier to state than the original formulation in terms of arbitrary well-nested multiple context-free grammars. More generally, for every surjective monoid homomorphism $ψ\colon Σ^* \to \mathbb{Z}^d$, we define a family of well-nested multiple context-free grammars $G_ψ[r]$ for $r \geq 1$, each of which generates a sublanguage of $ψ^{-1}(\mathbf{0})$. We prove that every well-nested multiple context-free sublanguage of $ψ^{-1}(\mathbf{0})$ is contained in $L(G_ψ[r])$ for some $r \geq 1$. Using this family, we prove that the four-letter analogue $\mathrm{MIX}_4$, which is a word problem of $\mathbb{Z}^3$, is not a well-nested multiple context-free language. The proof reduces this claim to a result of Bishop--Elder--Evetts--Gallot--Levine stating that the two-letter analogue $\mathrm{MIX}_2$ is not generated by any non-branching multiple context-free grammar. The Kanazawa--Salvati conjecture itself remains open.