Metraipolis › archive › dc_5bc057f882cb
On the Kanazawa--Salvati Conjecture — arXiv:2609.13871
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.13871
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T02:16:54.646Z
- SHA-256 of the archived text
97161b40d7d8258f26e53742c50a8c06e20b91e4c5227b871500ca6993b89d3f- Stable URL of this page
https://metraipolis.com/documento/dc_5bc057f882cb
How to cite
On the Kanazawa--Salvati Conjecture — arXiv:2609.13871 — arXiv (en), https://arxiv.org/abs/2609.13871 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5bc057f882cb (Metraipolis archive dc_5bc057f882cb, sha256 97161b40d7d8258f26e53742c50a8c06e20b91e4c5227b871500ca6993b89d3f)
BibTeX
@misc{dc5bc057f882cb,
title = {On the Kanazawa--Salvati Conjecture — arXiv:2609.13871},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.13871},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5bc057f882cb; sha256 97161b40d7d8258f26e53742c50a8c06e20b91e4c5227b871500ca6993b89d3f},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.13871. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\psi\colon \Sigma^* \to \mathbb{Z}^d$, we define a family of well-nested multiple context-free grammars $G_\psi[r]$ for $r \geq 1$, each of which generates a sublanguage of $\psi^{-1}(\mathbf{0})$. We prove that every well-nested multiple context-free sublanguage of $\psi^{-1}(\mathbf{0})$ is contained in $L(G_\psi[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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-15 in cs.FL).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2609.13871 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T01:56:58.265Z dalla pagina https://arxiv.org/catchup/cs.FL/2026-09-15?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).