A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913112848859136 |
|---|---|
| author | German, Samuel |
| author_facet | German, Samuel |
| contents | 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^{\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$. 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 $KL^{-1}$ cannot be empty when $K$ and $L$ are accepted by permutation automata with $\operatorname{asc}(K)=m$ and $\operatorname{asc}(L)=n$; this follows from the bijectivity of the transition action. Second, for every $m,n\ge 1$ and every $α\ge m$, we construct a ternary witness pair $(A^{\mathrm{q}}_{m,α},B^{\mathrm{q}}_{n,α})$ such that $\operatorname{asc}(L(A^{\mathrm{q}}_{m,α}))=m$, $\operatorname{asc}(L(B^{\mathrm{q}}_{n,α}))=n$, and $\operatorname{asc}(L(A^{\mathrm{q}}_{m,α})L(B^{\mathrm{q}}_{n,α})^{-1})=α$.
The high-range construction is group-theoretic: the words accepted by $B^{\mathrm{q}}_{n,α}$ induce exactly a point stabilizer in a symmetric group, and the standard quotient construction then saturates the original final set of $A^{\mathrm{q}}_{m,α}$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_10852 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata German, Samuel Formal Languages and Automata Theory Primary 68Q45, Secondary 68Q70, 20B30 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^{\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$. 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 $KL^{-1}$ cannot be empty when $K$ and $L$ are accepted by permutation automata with $\operatorname{asc}(K)=m$ and $\operatorname{asc}(L)=n$; this follows from the bijectivity of the transition action. Second, for every $m,n\ge 1$ and every $α\ge m$, we construct a ternary witness pair $(A^{\mathrm{q}}_{m,α},B^{\mathrm{q}}_{n,α})$ such that $\operatorname{asc}(L(A^{\mathrm{q}}_{m,α}))=m$, $\operatorname{asc}(L(B^{\mathrm{q}}_{n,α}))=n$, and $\operatorname{asc}(L(A^{\mathrm{q}}_{m,α})L(B^{\mathrm{q}}_{n,α})^{-1})=α$. The high-range construction is group-theoretic: the words accepted by $B^{\mathrm{q}}_{n,α}$ induce exactly a point stabilizer in a symmetric group, and the standard quotient construction then saturates the original final set of $A^{\mathrm{q}}_{m,α}$ 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. |
| title | A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata |
| topic | Formal Languages and Automata Theory Primary 68Q45, Secondary 68Q70, 20B30 |
| url | https://arxiv.org/abs/2605.10852 |