Metraipolis › archive › dc_46875d0db2a3

Undecidability of Adjacent Equality for Insertion, Shuffle, and Crossover Language Operations — arXiv:2608.27755

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.27755
License (as archived)
CC0-1.0
Archived
2026-10-17T11:57:12.463Z
SHA-256 of the archived text
75c2a56beee636d4ada8b5ab05deb27fdbd5f224bf18a3501642b4544af1d05e
Stable URL of this page
https://metraipolis.com/documento/dc_46875d0db2a3

How to cite

Undecidability of Adjacent Equality for Insertion, Shuffle, and Crossover Language Operations — arXiv:2608.27755 — arXiv (en), https://arxiv.org/abs/2608.27755 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_46875d0db2a3 (Metraipolis archive dc_46875d0db2a3, sha256 75c2a56beee636d4ada8b5ab05deb27fdbd5f224bf18a3501642b4544af1d05e)
BibTeX
@misc{dc46875d0db2a3,
  title = {Undecidability of Adjacent Equality for Insertion, Shuffle, and Crossover Language Operations — arXiv:2608.27755},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.27755},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_46875d0db2a3; sha256 75c2a56beee636d4ada8b5ab05deb27fdbd5f224bf18a3501642b4544af1d05e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27755. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

We study a family of language operations based on insertion, shuffle, and crossover and investigate the undecidability of adjacent equality together with finite convergence and associated spectrum questions. Insertion and shuffle operations on formal languages arise in formal language theory, models of concurrency, and biologically inspired computation. This paper studies a different question from the usual closure problem, specifically whether an increasing sequence of languages generated by repeated insertion, or by increasing the permitted degree of bounded shuffle, reaches an instance of adjacent equality after finitely many stages. We show that several such adjacent equality questions are undecidable. In particular, reaching such an adjacent equality event is undecidable for each of the following: iterated insertion of a regular language into a context-free language; bounded shuffle of a regular language with a context-free language as the bound increases; and the corresponding self-insertion and self-bounded-shuffle hierarchies for context-free languages. The new reductions proceed directly from the undecidability of context-free-language universality, using separator-delimited block constructions and, for self-operations, an absorbing regular language of guard violations. Earlier trace-based proofs relied on mortality and uniform halting. More generally, we investigate finite-stage equality and stabilization (persistent equality) in hierarchies generated by insertion and bounded shuffle. In addition to giving substantially simpler proofs of earlier undecidability results, we obtain general criteria for one-step equality, develop new reductions for self-insertion, and identify several open problems, including structural questions concerning insertion depth and degree whose resolution determines whether adjacent equality necessarily implies permanent stabilization.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-31 in cs.FL).
Categorie arXiv: Formal Languages and Automata Theory (cs.FL).
Pagina del lavoro: https://arxiv.org/abs/2608.27755 — 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-17T11:27:34.036Z dalla pagina https://arxiv.org/catchup/cs.FL/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).