Undecidability of Adjacent Equality for Insertion, Shuffle, and Crossover Language Operations
Formal Languages and Automata Theory
Summary
The authors explore certain operations on formal languages called insertion, shuffle, and crossover, focusing on whether sequences created by these operations eventually stop changing after a finite number of steps. They find that it is generally impossible (undecidable) to determine when such sequences reach a point of 'adjacent equality,' where two consecutive steps produce the same language. Their proofs build on known undecidability results about context-free languages and use new techniques that simplify previous approaches. The paper also raises open questions about when these sequences truly stabilize versus just temporarily appear to do so.
Authors
Charles E. Hughes
Abstract
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.