Exact Accepting-State Spectrum for Reversal of Permutation Automata

Abstract

We determine the accepting-state spectrum of reversal for permutation automata exactly, thereby proving the Rauch--Holzer conjecture on this operation. For every $m\ge 2$ and every $\alpha \ge 2$, we construct a binary permutation automaton $A_{m,\alpha }$ such that $\mathrm{asc}(L(A_{m,\alpha }))=m$ and $\mathrm{asc}(L(A_{m,\alpha }{)}^R)=\alpha$. Combined with the trivial cases $m=0$ and $m=1$, and with the previously known fact that $1$ is magic for every $m\ge 2$, this yields the exact spectrum $g_{R,\mathrm{PFA}}^{\mathrm{asc}}(0)=\{0\}$, $g_{R,\mathrm{PFA}}^{\mathrm{asc}}(1)=\{1\}$, and $g_{R,\mathrm{PFA}}^{\mathrm{asc}}(m)={\mathbb{N}}_{\ge 2}$ for every $m\ge 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 $\alpha$-subsets of $[n]$, where $n=m+\alpha -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.

Accepted to DCFS 2026; to appear in Springer LNCS