Exact Accepting-State Spectrum for Reversal of Permutation Automata

arXiv:2605.13385 · cs.FL · Submitted 2026-05-13 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Exact Accepting-State Spectrum for Reversal of Permutation Automata".

Jane: Here's the gist of the paper. Exact Accepting-State Spectrum for Reversal of Permutation Automata determines exactly that reversal has only one non-trivial obstruction on the accepting-state spectrum of permutation automata The main result proves a conjecture of Rauch and Holzer by showing that, once the trivial cases m = 0 and m = 1 are separated, the only magic value for reversal is 1 The Core Result The paper constructs a binary permutation automaton Am,α such that asc(L(Am,α)) = m and asc(L(Am,α)R) = α for every m ≥ 2 and every α ≥ 2 This construction yields the exact spectrum g asc R,PFA(m) = N≥2, if m ≥ 2 The proof is uniform and group-theoretic in flavor, using a witness family where the states of the forward automaton are the α-subsets of

n: , where n = m + α − 1 This demonstrates that reversal imposes only one nontrivial obstruction on the accepting-state spectrum of permutation automata: the value 1 remains magic for every m ≥ 2, but every larger value is attainable.

Tom: Construction of the Witness Family The witness family is based on the natural action of Sn on the family of α-subsets of

n: , where n = m + α − 1 The alphabet is Σ = a, b, where 'a' acts as the n-cycle (1 2...

Jane: n) and 'b' acts as the transposition (1 2) The automaton Am,α is defined with Q:=

n: α and F:= S(T0), where T0 =

n: α−1 This construction ensures that the automaton is a binary permutation automaton because 'a' and 'b' generate Sn.

Tom: Characterization of Reachable States The reachable states of the reverse automaton ARm,α are exactly the stars S(T) for T ∈

n: α−1 The accepting states among these reachable states are precisely those where T ⊆ qI, where qI is the original initial state This results in exactly α accepting states in the reachable part of ARm,α.

Paper summary: Tom: So to recap, this paper, "Exact Accepting-State Spectrum for Reversal of Permutation Automata," sets out to determine the exact accepting state spectrum for reversing languages in permutation automata >

Jane: They achieve this by constructing a specific type of binary permutation automaton, Am alpha, where they can control the accepting state count for the original language to be m and the reversed language to be alpha >

Lu: The construction is uniform across all these m and alpha values, using a witness family based on subsets of n, where n equals m plus alpha minus one >

Meng: That sounds complex. Is this construction just theoretical, or does it have any practical implication for how we model language operations at scale >

Tom: It's uniform group-theoretic flavor, which suggests the structure is robust across different settings rather than a one-off trick >

Jane: The core result they prove is that for every m greater than two and every alpha greater than two, you can find this automaton Am alpha that hits those specific counts >

Lalam: And they show that this proves the conjecture made by Rauch and Holzer about reversal, which was about finding a single obstruction >

Conclusion: Tom: So what's the real meaning of this paper? It essentially settles the question about how reversal affects the accepting state complexity for these permutation automata >

Jane: It confirms that after you handle the simple cases where m is zero or one, there's only one specific value, which is one, that acts as an obstruction for reversal across all larger numbers >

Lu: The result they proved shows that you can always construct a case for any pair of m and alpha greater than two using this construction >

Meng: For me, what this means is that if we are designing systems where the language structure is defined by permutations, we know exactly where to look for the complexity limit on reversal >

Tom: It tells us that even with complicated operations like reversal, the complexity isn't completely unpredictable; it just has one specific sticking point at value one >

University of California, San Diego, USA

cs.FL

Submitted: 2026-05-13

Updated: 2026-11-12

Comments: 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

Journal ref: 27th International Conference on Descriptional Complexity of Formal Systems (DCFS 2026), Lecture Notes in Computer Science, vol. 16681, pp. 74-82, Springer (2027)

DOI: 10.1007/978-3-032-32016-2_6

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 85/100

The gist: Exact Accepting-State Spectrum for Reversal of Permutation Automata determines exactly that reversal has only one non-trivial obstruction on the accepting-state spectrum of permutation automata The…

Key concepts

Binary Permutation Automaton
This is a specific type of deterministic automaton where the set of states and transitions are governed by permutations acting on a set. In this paper, the states are subsets of $[n]$, and the transitions are defined by actions like an $n$-cycle and a transposition, which generate the symmetric group $S_n$. This structure is key to linking automata theory with permutation groups.
Accepting-State Spectrum
This refers to the set of possible numbers of accepting states for a given language or automaton operation. The paper determines this spectrum exactly for reversal operations on permutation automata, showing that the only non-trivial obstruction is the value 1, implying a simple structure for these counts.
Reversal Operation
Reversal is an operation applied to a permutation automaton's language. The goal is to understand how this reversal affects the number of accepting states. The construction shows that after reversal, the reachable states are precisely the stars defined by certain subsets, allowing for precise counting of accepting states.
Witness Family
This is a specific set of structures used in the proof to establish existence. The paper uses a uniform group-theoretic witness family based on $\alpha$-subsets of $[n]$ under the action of $S_n$ generated by an $n$-cycle and a transposition. This family provides the necessary mathematical framework to construct the required automaton $Am, \alpha$.

Terminology

Summary

Exact Accepting-State Spectrum for Reversal of Permutation Automata determines exactly that reversal has only one non-trivial obstruction on the accepting-state spectrum of permutation automata The main result proves a conjecture of Rauch and Holzer by showing that, once the trivial cases m = 0 and m = 1 are separated, the only magic value for reversal is 1

The Core Result

The paper constructs a binary permutation automaton Am,α such that asc(L(Am,α)) = m and asc(L(Am,α)R) = α for every m ≥ 2 and every α ≥ 2 This construction yields the exact spectrum g asc R,PFA(m) = N≥2, if m ≥ 2 The proof is uniform and group-theoretic in flavor, using a witness family where the states of the forward automaton are the α-subsets of [n], where n = m + α − 1 This demonstrates that reversal imposes only one nontrivial obstruction on the accepting-state spectrum of permutation automata: the value 1 remains magic for every m ≥ 2, but every larger value is attainable.

Construction of the Witness Family

The witness family is based on the natural action of Sn on the family of α-subsets of [n], where n = m + α − 1 The alphabet is Σ = a, b, where 'a' acts as the n-cycle (1 2... n) and 'b' acts as the transposition (1 2) The automaton Am,α is defined with Q:= [n]α and F:= S(T0), where T0 = [n]α−1 This construction ensures that the automaton is a binary permutation automaton because 'a' and 'b' generate Sn.

Characterization of Reachable States

The reachable states of the reverse automaton ARm,α are exactly the stars S(T) for T ∈ [n]α−1 The accepting states among these reachable states are precisely those where T ⊆ qI, where qI is the original initial state This results in exactly α accepting states in the reachable part of ARm,α.

Conclusion on the Spectrum

The exact spectrum g asc R,PFA(m) is determined to be:

**/g asc R,PFA(m) = N≥2, if m ≥ 2 **

Worked Example

A worked example with m = 3 shows that for A3,4, the reachable part of AR 3,4 has exactly 4 accepting states This is illustrated by explicitly listing the four stars whose centers are 3-subsets of qI = 1234.

Corollary Summary

The corollary confirms that g asc R,PFA(m) = N≥2, if m ≥ 2 This proves the conjecture of Rauch and Holzer [5, Conjecture 3.25].

References

[1] Dassow, J.: On the number of accepting states of finite automata

[2] Dixon, J.D., Mortimer, B. p. 3: Permutation Groups, Graduate Texts in Mathematics, vol. p. 8 163

[3] Hospodár, M., Mlynárčik, P. p. 1: Operations on permutation automata

[4] McNaughton, R.: The loop complexity of pure-group events

[5] Rauch, C., Holzer, M. p. 0: On the accepting state complexity of operations on permutation automata

[6] Thierrin, G.: Permutation automata

--- Page 1 ---

Exact Accepting-State Spectrum for Reversal of Permutation Automata Samuel German University of California, San Diego, USA sgerman@ucsd.edu Abstract. p. 0 We determine the accepting-state spectrum of reversal for permutation automata exactly, thereby proving the Rauch–Holzer conjecture on this operation. p. 0 For every m ≥ 2 and every α ≥ 2, we construct a binary permutation automaton Am,α such that asc(L(Am,α)) = m and asc(L(Am,α)R) = α. p. 0 Combined with the trivial cases m = 0 and m = 1, and with the previously known fact that 1 is magic for every m ≥ 2, this yields the exact spectrum g asc R,PFA(m) =

N≥2, if m ≥ 2. Thus reversal has, for permutation automata, the simplest possible exact accepting-state spectrum compatible with the single nontrivial obstruction at value 1. p. 0 p. 0 p. 0 The proof uses a uniform group-theoretic witness family: the states of the forward automaton are the α-subsets of [n], where n=m+α−1, under the action generated by an n-cycle and a transposition, while the accepting states form a single star family. p. 0 p. 0 p. 0 After reversal, the reachable subset-states are exactly the stars, which makes it possible to count the accepting reachable states precisely and to prove minimality of the reachable reverse automaton. p. 0 p. 0 p. 0 p. 0 Keywords: accepting-state complexity; permutation automata; reversal; exact spectrum; magic numbers

--- Page 2 ---

Samuel German Permutation automata are a classical subclass of deterministic automata, with early connections to group languages and pure-group events appearing already in the work of McNaughton [4] and Thierrin [6]; see also Hospodár and Mlynárčik [3] for a modern treatment of operations on permutation automata. Building on this line, Rauch and Holzer [5] initiated the systematic study of accepting-state complexity for operations on permutation automata. p. 1 p. 1 Among the operations they considered, reversal remained one of the few cases whose exact accepting-state spectrum was not completely determined. p. 1 p. 1 For reversal, Rauch and Holzer proved that the value 1 is magic for every m ≥ 2, completely settled the case m = 2, and conjectured that no further obstruction exists [5]. p. 1 p. 1 Our contribution is a constructive proof of this conjecture. p. 1 p. 1 More precisely, for every m ≥ 2 and every α ≥ 2, we construct a binary permutation automaton Am,α such that asc(L(Am,α)) = m and asc(L(Am,α)R) = α. p. 1 p. 1 Equivalently, we obtain the exact spectrum g asc R,PFA(m) =



N≥2, if m ≥ 2. Thus reversal has, for permutation automata, the simplest possible exact accepting-state spectrum compatible with the single nontrivial obstruction at value 1. The proof uses a uniform group-theoretic witness family: the states of the forward automaton are the α-subsets of [n], where n=m+α−1, under the action generated by an n-cycle and a transposition, while the accepting states form a single star family. After reversal, the reachable subset-states are exactly the stars, which makes it possible to count the accepting reachable states precisely and to prove minimality of the reachable reverse automaton.

--- Page 3 ---

2 Samuel German Permutation automata are a classical subclass of deterministic automata, with early connections to group languages and pure-group events appearing already in the work of McNaughton [4] and Thierrin [6]; see also Hospodár and Mlynárčik [3] for a modern treatment of operations on permutation automata. Building on this line, Rauch and Holzer [5] initiated the systematic study of accepting-state complexity for operations on permutation automata. Among the operations they considered, reversal remained one of the few cases whose exact accepting-state spectrum was not completely determined. For reversal, Rauch and Holzer proved that the value 1 is magic for every m ≥ 2, completely settled the case m = 2, and conjectured that no further obstruction exists [5]. Our contribution is a constructive proof of this conjecture. More precisely, for every m ≥ 2 and every α ≥ 2, we construct a binary permutation automaton Am,α such that asc(L(Am,α)) = m and asc(L(Am,α)R) = α. Equivalently, we obtain the exact spectrum g asc R,PFA(m) =



N≥2, if m ≥ 2. Thus reversal has, for permutation automata, the simplest possible exact accepting-state spectrum compatible with the single nontrivial obstruction at value 1. The proof uses a uniform group-theoretic witness family: the states of the forward automaton are the α-subsets of [n], where n=m+α−1, under the action generated by an n-cycle and a transposition, while the accepting states form a single star family. After reversal, the reachable subset-states are exactly the stars, which makes it possible to count the accepting reachable states precisely and to prove minimality of the reachable reverse automaton.

--- Page 4 ---

Samuel German The proof uses a uniform group-theoretic witness family: the states of the forward automaton are the α-subsets of [n], where n=m+α−1, under the action generated by an n-cycle and a transposition, while the accepting states form a single star family. After reversal, the reachable subset-states are exactly the stars, which makes it possible to count the accepting reachable states precisely and to prove minimality of the reachable reverse automaton.

--- Page 5 ---

Exact Accepting-State Spectrum for Reversal of Permutation Automata We now determine the reversal spectrum exactly. The cases m = 0 and m = 1 will be handled at the end of this section, so throughout this section we fix integers m ≥ 2 and α ≥ 2, and set n:= m + α − 1. p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 Our witness family is based on the natural action of Sn on the family of α-subsets of [n]. p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 Let Q:= [n]α, qI:= Σ(1,. p. 2 p. 2 p. 2 p. 2 p. 2 p. 2 p. 2.., α), and T0:= Σ(1,..., α − 1). For each T ∈ [n]α−1, define S(T):= Σ(X ∈ Q T ⊆ X). p. 2 p. 2 p. 2 p. 2 p. 2 p. 2 p. 2 In particular, S(T0) is the family of all α-subsets of [n] containing T0. p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 Let the alphabet be Σ = a, b, where the letter a acts on [n] as the n-cycle (1 2. p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4.. n) and the letter b acts on [n] as the transposition (1 2). p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 These actions induce permutations of Q by X · a:= Σ(iα i ∈ X), X · b:= Σ(iβ i ∈ X) for all X ∈ Q. p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 Finally, let F = S(T0), and define Am,α = (Q, Σ, ·, qI, F). p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 Since a and b generate Sn [2], the automaton Am,α is a binary permutation automaton. p. 4 p. 4 p. 4 p. 4 p. 4 p. 4 p. 4

--- Page 6 ---

Exact Spectrum of Reversal We now determine the reversal spectrum exactly. The cases m = 0 and m = 1 will be handled at the end of this section, so throughout this section we fix integers m ≥ 2 and α ≥ 2, and set n:= m + α − 1. Our witness family is based on the natural action of Sn on the family of α-subsets of [n]. Let Q:= [n]α, qI:= Σ(1,..., α), and T0:= Σ(1,..., α − 1). For each T ∈ [n]α−1, define S(T):= Σ(X ∈ Q T ⊆ X). In particular, S(T0) is the family of all α-subsets of [n] containing T0. Let the alphabet be Σ = a, b, where the letter a acts on [n] as the n-cycle (1 2... n) and the letter b acts on [n] as the transposition (1 2). These actions induce permutations of Q by X · a:= Σ(iα i ∈ X), X · b:= Σ(iβ i ∈ X) for all X ∈ Q. Finally, let F = S(T0), and define Am,α = (Q, Σ, ·, qI, F). Since a and b generate Sn [2], the automaton Am,α is a binary permutation automaton.

--- Page 7 ---

Exact Spectrum of Reversal We now determine the reversal spectrum exactly. The cases m = 0 and m = 1 will be handled at the end of this section, so throughout this section we fix integers m ≥ 2 and α ≥ 2, and set n:= m + α − 1. Our witness family is based on the natural action of Sn on the family of α-subsets of [n]. Let Q:= [n]α, qI:= Σ(1,..., α), and T0:= Σ(1,..., α − 1). For each T ∈ [n]α−1, define S(T):= Σ(X ∈ Q T ⊆ X). In particular, S(T0) is the family of all α-subsets of [n] containing T0. Let the alphabet be Σ = a, b, where the letter a acts on [n] as the n-cycle (1 2... n) and the letter b acts on [n] as the transposition (1 2). These actions induce permutations of Q by X · a:= Σ(iα i ∈ X), X · b:= Σ(iβ i ∈ X) for all X ∈ Q. Finally, let F = S(T0), and define Am,α = (Q, Σ, ·, qI, F). Since a and b generate Sn [2], the automaton Am,α is a binary permutation automaton.

--- Page 8 ---

Exact Spectrum of Reversal We now determine the reversal spectrum exactly. The cases m = 0 and m = 1 will be handled at the end of this section, so throughout this section we fix integers m ≥ 2 and α ≥ 2, and set n:= m + α − 1. Our witness family is based on the natural action of Sn on the family of α-subsets of [n]. Let Q:= [n]α, qI:= Σ(1,..., α), and T0:= Σ(1,..., α − 1). For each T ∈ [n]α−1, define S(T):= Σ(X ∈ Q T ⊆ X). In particular, S(T0) is the family of all α-subsets of [n] containing T0. Let the alphabet be Σ = a, b, where the letter a acts on [n] as the n-cycle (1 2... n) and the letter b acts on [n] as the transposition (1 2). These actions induce permutations of Q by X · a:= Σ(iα i ∈ X), X · b:= Σ(iβ i ∈ X) for all X ∈ Q. Finally, let F = S(T0), and define Am,α = (Q, Σ, ·, qI, F). Since a and b generate Sn [2], the automaton Am,α is a binary permutation automaton.

--- Page 9 ---

Exact Spectrum of Reversal We now determine the reversal spectrum exactly. The cases m = 0 and m = 1 will be handled at the end of this section, so throughout this section we fix integers m ≥ 2 and α ≥ 2, and set n:= m + α − 1. Our witness family is based on the natural action of Sn on the family of α-subsets of [n]. Let Q:= [n]α, qI:= Σ(1,..., α), and T0:= Σ(1,..., α − 1). For each T ∈ [n]α−1, define S(T):= Σ(X ∈ Q T ⊆ X). In particular, S(T0) is the family of all α-subsets of [n] containing T0. Let the alphabet be Σ = a, b, where the letter a acts on [n] as the n-cycle (1 2... n) and the letter b acts on [n] as the transposition (1 2). These actions induce permutations of Q by X · a:= Σ(iα i ∈ X), X · b:= Σ(iβ i ∈ X) for all X ∈ Q. Finally, let F = S(T0), and define Am,α = (Q, Σ, ·, qI, F). Since a and b generate Sn [2], the automaton Am,α is a binary permutation automaton.

--- Page 10 ---

Exact Spectrum of Reversal We now determine the reversal spectrum exactly. The cases m = 0 and m = 1 will be handled at the end of this section, so throughout this section we fix integers m ≥ 2 and α ≥ 2, and set n:= m + α − 1. Our witness family is based on the natural action of Sn on the family of α-subsets of [n]. Let Q:= [n]α, qI:= Σ(1,..., α), and T0:= Σ(1,..., α − 1). For each T ∈ [n]α−1, define S(T):= Σ(X ∈ Q T ⊆ X). In particular, S(T0) is the family of all α-subsets of [n] containing T0. Let the alphabet be Σ = a, b, where the letter a acts on [n] as the n-cycle (1 2... n) and the letter b acts on [n] as the transposition (1 2). These actions induce permutations of Q by X · a:= Σ(iα i ∈ X), X · b:= Σ(iβ i ∈ X) for all X ∈ Q. Finally, let F = S(T0), and define Am,α = (Q, Σ, ·, qI, F). Since a and b generate Sn [2], the automaton Am,α is a binary permutation automaton.

--- Page 11 ---

Exact Spectrum of Reversal We now determine the reversal spectrum exactly. The cases m = 0 and m = 1 will be handled at the end of this section, so throughout this section we fix integers m ≥ 2 and α ≥ 2, and set n:= m + α − 1. Our witness family is based on the natural action of Sn on the family of α-subsets of [n]. Let Q:= [n]α, qI:= Σ(1,..., α), and T0:= Σ(1,..., α − 1). For each T ∈ [n]α−1, define S(T):= Σ(X ∈ Q T ⊆ X). In particular, S(T0) is the family of all α-subsets of [n] containing T0. Let the alphabet be Σ = a, b, where the letter a acts on [n] as the n-cycle (1 2... n) and the letter b acts on [n] as the transposition (1 2). These actions induce permutations of Q by X · a:= Σ(iα i ∈ X), X · b:= Σ(iβ i ∈ X) for all X ∈ Q. Finally, let F = S(T0), and define Am,α = (Q, Σ, ·, qI, F). Since a and b generate Sn [2], the automaton Am,α is a binary permutation automaton.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved analysis of reversal operations for permutation automata can be achieved by constructing binary permutation automata Am,alpha such that asc(L(Am,alpha)) equals m and asc(L(Am,alpha)R) equals alpha for any m >= 2 and alpha >= 2.

  2. The improved system can precisely determine the exact spectrum gascRPFA(m) as a function of m: it is zero if m=0, one if m=1, and N greater than or equal to 2 if m greater than or equal to 2.

  3. The system can provide a constructive proof for the Rauch–Holzer conjecture by utilizing a uniform group-theoretic witness family: the states of the forward automaton are the alpha-subsets of [n], where n equals m plus alpha minus 1, under an action generated by an n-cycle and a transposition.

  4. The improved AI can identify that reversal has the simplest possible exact accepting-state spectrum compatible with the single nontrivial obstruction at value 1, meaning it is only obstructed at value one for all m >= 2.

  5. The system can perform concrete calculations, such as for m = 3 and alpha = 4, explicitly listing the four reachable stars S(T) whose centers are 3-subsets of qI = 1234, confirming that the reachable part has exactly four accepting states (which is alpha).

Related papers