arXiv:2605.10852 · v2
A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
摘要
This paper determines the accepting-state spectrum of the right-quotient operation for permutation automata, solving an open problem posed by Rauch and Holzer. They showed that in the unary case in which the languages whose right quotient we consider are languages over an alphabet with but one symbol, the accepting state complexities which could ensue for automata recognizing their quotient is exactly all integers between $1$ and $mn$ inclusive when $m,n \ge 1$; we show that for arbitrary alphabets the accepting-state spectrum is $g^{\operatorname{asc}}_{-1,\mathrm{PFA}}(m,n)=\{0\}$ if $m=0$ or $n=0$, and $g^{\operatorname{asc}}_{-1,\mathrm{PFA}}(m,n)=\mathbb{N}_{>0}$ if $m,n\ge 1$. Our result shows that every positive accepting-state complexity ensues for right quotient as long as both of the languages of which we consider the right quotient are nonempty. $0$ becomes the only unavoidable magic value. Moreover, we show that an alphabet with just two letters can witness any arbitrary $α\ge 1$ when $m,n \ge 1$, in that languages can be defined over a binary alphabet with accepting-state complexity $m$ and $n$ respectively for which their right quotient has accepting-state complexity $α$. What ultimately happens in our proof is that we construct $(A^{\mathrm q}_{m,α},B^{\mathrm q}_{n,α})$ such that the words accepted by $B^{\mathrm q}_{n,α}$ induce a point stabilizer in a symmetric group, and the standard quotient construction giving an automaton recognizing the quotient language then saturates the original final set of $A^{\mathrm q}_{m,α}$ to a full orbit; this gives a minimal quotient automaton with exactly $α$ final states. The complete spectrum which is our result follows from this, solving the open question of what the right quotient's accepting-state complexity for permutation automata is.
作者备注：This version strengthens our result by showing that an alphabet with 2 letters can be used to realize, for any integers $m,n \ge 1$, any integer $α\ge 1$ being in the accepting-state spectrum of the right quotient operation for permutation automata; our proof previously used an alphabet with 3 letters with targets $α\ge m$. 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. 83-93, Springer (2027)