2026/05/11 by Samuel German · 1 voice
Computer Science · #cs.FL
paper · pdf · doi:10.48550/arxiv.2605.10852
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 gasc-1,PFA(m,n)=\0\ if m=0 or n=0, and gasc-1,PFA(m,n)=ℕ>0 if m,n≥ 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≥ 1, then the quotient language KL-1 cannot be empty when K and L are accepted by permutation automata with asc(K)=m and asc(L)=n; this follows from the bijectivity of the transition action. Second, for every m,n≥ 1 and every α≥ m, we construct a ternary witness pair (Aqm,α,Bqn,α) such that asc(L(Aqm,α))=m, asc(L(Bqn,α))=n, and asc(L(Aqm,α)L(Bqn,α)-1)=α. The high-range construction is group-theoretic: the words accepted by Bqn,α induce exactly a point stabilizer in a symmetric group, and the standard quotient construction then saturates the original final set of Aqm,α to a full orbit, yielding a minimal quotient automaton with exactly α 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.