Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2605.13385 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914563255959552 |
|---|---|
| author | German, Samuel |
| author_facet | German, Samuel |
| contents | 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 $α\ge 2$, we construct a binary permutation automaton $A_{m,α}$ such that $\operatorname{asc}(L(A_{m,α}))=m$ and $\operatorname{asc}(L(A_{m,α})^R)=α$. 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^{\operatorname{asc}}_{R,\mathrm{PFA}}(0)=\{0\}$, $g^{\operatorname{asc}}_{R,\mathrm{PFA}}(1)=\{1\}$, and $g^{\operatorname{asc}}_{R,\mathrm{PFA}}(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 $α$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_13385 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Exact Accepting-State Spectrum for Reversal of Permutation Automata German, Samuel Formal Languages and Automata Theory 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 $α\ge 2$, we construct a binary permutation automaton $A_{m,α}$ such that $\operatorname{asc}(L(A_{m,α}))=m$ and $\operatorname{asc}(L(A_{m,α})^R)=α$. 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^{\operatorname{asc}}_{R,\mathrm{PFA}}(0)=\{0\}$, $g^{\operatorname{asc}}_{R,\mathrm{PFA}}(1)=\{1\}$, and $g^{\operatorname{asc}}_{R,\mathrm{PFA}}(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 $α$-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. |
| title | Exact Accepting-State Spectrum for Reversal of Permutation Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2605.13385 |