A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata

Abstract

This paper resolves the open larger-alphabet quotient case in the accepting-state complexity theory of permutation automata. Rauch and Holzer showed that, in the unary setting, the attainable right-quotient accepting-state complexities are exactly $[1,mn]$. We prove that over arbitrary alphabets the exact spectrum is $g_{-1,\mathrm{PFA}}^{\mathrm{asc}}(m,n)=\{0\}$ if $m=0$ or $n=0$, and $g_{-1,\mathrm{PFA}}^{\mathrm{asc}}(m,n)={\mathbb{N}}_{>0}$ if $m,n\ge 1$. Thus, once both input languages are nonempty, every positive accepting-state complexity is attainable for right quotient, and $0$ is the only unavoidable magic value. The proof has two parts. First, we show that if $m,n\ge 1$, then the quotient language $K{L}^{-1}$ cannot be empty when $K$ and $L$ are accepted by permutation automata with $\mathrm{asc}(K)=m$ and $\mathrm{asc}(L)=n$; this follows from the bijectivity of the transition action. Second, for every $m,n\ge 1$ and every $\alpha \ge m$, we construct a ternary witness pair $(A_{m,\alpha }^{\mathrm{q}},B_{n,\alpha }^{\mathrm{q}})$ such that $\mathrm{asc}(L(A_{m,\alpha }^{\mathrm{q}}))=m$, $\mathrm{asc}(L(B_{n,\alpha }^{\mathrm{q}}))=n$, and $\mathrm{asc}(L(A_{m,\alpha }^{\mathrm{q}})L(B_{n,\alpha }^{\mathrm{q}}{)}^{-1})=\alpha$. The high-range construction is group-theoretic: the words accepted by $B_{n,\alpha }^{\mathrm{q}}$ induce exactly a point stabilizer in a symmetric group, and the standard quotient construction then saturates the original final set of $A_{m,\alpha }^{\mathrm{q}}$ to a full orbit, yielding a minimal quotient automaton with exactly $\alpha$ final states. Combined with the known unary interval $[1,mn]$, this yields the complete spectrum and resolves the larger-alphabet right-quotient case for permutation automata.

Accepted to DCFS 2026; proceedings version to appear in Springer LNCS