State-Primality Is Undecidable for Deterministic One-Counter Automata
Alp Eren Bütün · Zenodo (CERN European Organization for Nuclear Research) · 2026
A deterministic one-counter automaton (DOCA) presentation is state-prime if its language cannot be represented as a finite intersection of DOCA superlanguages recognized with strictly fewer control states than the presented automaton. Totzke posed decidability of this property as Automata Exchange problem 20.03. We prove that the problem is undecidable. The proof is a many-one reduction from deterministic two-counter-machine halting. Its central device is an elementary-abelian permutation core on V = (Z2 )d . The core section rejecting only the identity is prime by the permutation-DFA theorem of Kupferman and Mosheiff, whereas every additional rejected group element yields a canonical quotient factor on V /⟨r⟩ with exactly half as many states. We couple this asymmetry to three predicates for a proposed two-counter computation: regular control-flow consistency and the two independent counter trajectories. If the source machine halts, a fixed-suffix section of the target is exactly the prime permutation language; if it does not halt, the entire target language is exactly the intersection of explicit half-size quotient DOCAs. The reduction already works for complete real-time deterministic one-counter automata with one work symbol, all control states final, and counter updates in {−1, 0, +1}.