2026/05/13 by Samuel German · 1 voice
Computer Science · #cs.FL
paper · pdf · doi:10.48550/arxiv.2605.13385
We determine the accepting-state spectrum of reversal for permutation automata exactly, thereby proving the Rauch--Holzer conjecture on this operation. For every m ≥ 2 and every α≥ 2, we construct a binary permutation automaton Am,α such that asc(L(Am,α))=m and asc(L(Am,α)R)=α. Combined with the trivial cases m=0 and m=1, and with the previously known fact that 1 is magic for every m ≥ 2, this yields the exact spectrum gascR,PFA(0)=\0\, gascR,PFA(1)=\1\, and gascR,PFA(m)=ℕ≥ 2 for every m ≥ 2. Thus reversal has, for permutation automata, the simplest possible exact accepting-state spectrum compatible with the single nontrivial obstruction at value 1. The proof uses a uniform group-theoretic witness family: the states of the forward automaton are the α-subsets of [n], where n=m+α-1, under the action generated by an n-cycle and a transposition, while the accepting states form a single star family. After reversal, the reachable subset-states are exactly the stars. This makes it possible to count the accepting reachable states precisely and to prove minimality of the reachable reverse automaton.