arXiv:2605.13385 · v2
Exact Accepting-State Spectrum for Reversal of Permutation Automata
摘要
In this paper we determine the accepting-state spectrum of the reversal operation on permutation automata, and moreover prove the conjecture conjectured by Rauch and Holzer in so doing. Namely, we show that reversal satisfies the 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 $m\ge 2$. We do this by, for every $m\ge 2$ and every $α\ge 2$, constructing a binary permutation automaton $A_{m,α}$ such that $ \operatorname{asc}(L(A_{m,α}))=m$ and $ \operatorname{asc}(L(A_{m,α})^{R})=α$. The spectrum above follows from this (combined with the trivial cases $m=0$ and $m=1$ and the fact that $1$ is magic for every $m\ge 2$). Thus our result shows that for $m \ge 2$, the reversal operation in permutation automaton attains ever single value positive value in the accepting-state complexity except for $1$.
作者备注：This version strengthens our result by, $m,α\ge 2$, constructing a language $L$ with $\operatorname{asc}(L)=m$ and $\operatorname{asc}(L^R)=α$ such that the minimal DFAs recognizing $L$ and $L^R$ each have polynomially many states in $m$ and $α$, whereas the proof previously could use exponentially many states here. This version also streamlines the exposition
期刊信息：27th International Conference on Descriptional Complexity of Formal Systems (DCFS 2026), Lecture Notes in Computer Science, vol. 16681, pp. 74-82, Springer (2027)