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

arXiv:2605.10852 · cs.FL · Submitted 2026-05-11 · 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: "A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata".

Jane: Here's the gist of the paper. A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata resolves the open larger-alphabet quotient case in accepting-state complexity theory of permutation automata by showing that over arbitrary alphabets, every positive acceptingstate complexity is attainable for right quotient when both input languages are nonempty The Main Contribution The main contribution of this paper is a complete solution of the larger-alphabet right-quotient problem left open by Rauch and Holzer

4: The authors show that once the alphabet is allowed to be nonunary, the spectrum becomes complete, meaning every positive integer occurs as the accepting-state complexity of a right quotient of two permutation-automaton languages with prescribed positive accepting-state complexities Over arbitrary alphabets, the exact spectrum is gasc−1,PFA(m, n) = ((if m = 0 or n = 0, N>0, if m, n ≥ 1 Structural Consequences of Non-Emptiness The proof begins by showing a structural consequence of bijectivity for nonempty inputs First, the authors show that if m, n ≥ 1, then asc(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 Construction of the High-Range Spectrum For every m, n ≥ 1 and every α ≥ m, a ternary witness pair (Aq m,α, Bq n,α) is constructed such that asc(L(A q m,α)) = m and asc(L(B q n,α)) = n The high-range construction is group-theoretic Specifically, the automaton Bq n,α acts on

k: × Zn+1 where k = α + 1 This design ensures that the permutations induced on the first coordinate are exactly the point stabilizer StabSk(k) The Complete Spectrum Result Combined with the known unary interval

1, mn: , this yields the complete spectrum and resolves the larger-alphabet right-quotient case for permutation automata The final theorem states that for all m, n ≥ 0, gasc−1,PFA(m, n) = ((if m = 0 or n = 0, N>0, if m, n ≥ 1 The Unavoidable Magic Value The paper establishes that once both input languages are nonempty, every positive acceptingstate complexity is attainable for right quotient and 0 is the only unavoidable magic value This demonstrates a genuine phase transition from the unary to the nonunary setting The Unary Case Foundation The unary result,

1, mn: , is established by Rauch and Holzer This rigidity is shown to be entirely unary, suggesting that the larger-alphabet case is not representative of the general setting The Role of Stabilizer Actions The mechanism behind the nonunary spectrum is characterized by the availability of a stabilizer action that expands the quotient final set across a large orbit This is demonstrated by Lemma 5, which proves that Gn α = StabSk(k) The Low-Range Coverage The low range is covered by the unary witnesses of Rauch and Holzer Proposition 3 confirms that for all m, n ≥ 1 and all α ∈ N, every value in the low range is realized The Complete Spectrum Conclusion Since mn ≥ m, the sets of values from the low range and the high range together cover all positive integers N>0 for m, n ≥ 1 Therefore gasc−1,PFA(m, n) = N>0 for m, n ≥ 1 The Zero Case Resolution If m = 0 or n = 0, then any languages K, L with asc(K) = m and asc(L) = n satisfy K = ∅ or L = ∅, and therefore KL−1 = ∅ This proves gasc−1,PFA(m, n) = 0 if m = 0 or n = 0 The Unary Language Construction To prove the zero case attainment, the paper introduces a unary language Ut defined by Ct:=

t + 1: , p · a ≡ p + 1 (mod t + 1) for t ≥ 1 This automaton is a permutation automaton with exactly t final states, and Proposition 1 gives asc(L(Ct)) = t The High-Range Witness Construction Details The witness pair construction involves defining the alphabet as Σ:= (a, b, c) on

k: , where a = (1 2...

Tom: k), b = (1 2), and c = id

k: The transition function for Bq n,α is given by the specific rules involving addition modulo n + 1 The Minimal Quotient Automaton Lemma 7 confirms that the quotient automaton Aq m,α/Bq n,α is minimal This minimality leads directly to the conclusion that ascL(A q m,α)L(B q n,α)−1 = k − 1 = α The Final Theorem Statement Theorem 1 states that for all m, n ≥ 0, gasc−1,PFA(m, n) = ((if m = 0 or n = 0, N>0, if m, n ≥ 1 This resolves the larger-alphabet right-quotient case left open by Rauch and Holzer

4: The Expansion of Lemma 5 Proof An expanded proof of Lemma 5 shows that every adjacent transposition on

k − 1: is induced by a positive word over the alphabet, which is crucial for realizing the stabilizer elements This realization allows the construction of words x ∈ L(Bq n,α) corresponding to any element in StabSk(k) The Group-Theoretic Core The group-theoretic core involves showing that Gn α = StabSk(k) This is achieved by demonstrating that every element in StabSk(k) can be realized as the permutation induced by a word in L(Bq n,α) The Final Set Calculation Lemma 6 computes the final set of the quotient automaton as Fe =

h∈Gn α h−1(FA) = [h∈StabSk(k) h−1(FA): and concludes that Fe = (1,..., k − 1) This confirms ascL(A q m,α)L(B q n,α)−1 = α The Unary Interval Realization Proposition 3 confirms that for all m, n ≥ 1 and all α ∈ N, every value in the low range is realized by unary permutation automata This provides the foundation for covering the positive part of the spectrum The Final Conclusion on Attainability Since mn ≥ m, the sets of values from both ranges together equal N>0 for m, n ≥ 1 Therefore gasc−1,PFA(m, n) = N>0 for m, n ≥ 1 This resolves the larger-alphabet right-quotient case for permutation automata The Unavoidable Zero Conclusion The paper concludes that beyond the structural impossibility of 0 for nonempty inputs, the spectrum is complete This shows that right quotient for permutation automata undergoes a genuine phase transition from the unary to the nonunary setting The Definition of Right Quotient For languages K, L ⊆ Σ∗, the right quotient of K by L is KL−1:= ∃y ∈ L: xy ∈ K This operation is central to the study of accepting-state complexity in this context The Definition of Accepting-State Complexity Accepting-state complexity, asc(L), measures descriptional complexity by minimizing the number of accepting states rather than the total number of states Proposition 1 identifies this as F for a minimal DFA The Definition of Permutation Automaton A permutation automaton is a DFA in which, for every a ∈ Σ, the map q 7→ q ·a is a permutation of Q This property allows for the analysis using group actions The Definition of Right Quotient Language The language L(A/B) = L(A)L(B)−1 Lemma 3 provides the formal definition for how the quotient language relates to the original languages The Definition of Orbit Action If G ≤ Sn, then G acts on

n: by iπ = π(i) for i ∈

n: and π ∈ G, and we write iG:= ∃ π∈G iπ for the corresponding orbit This notation is used to describe the action of permutation groups The Definition of Point Stabilizer StabG(i):= ∃ π ∈ G iπ = i for the point stabilizer of i This concept is used to characterize the structure of the induced permutations The Definition of Induced Permutation If w = c1c2 · · · cr, then the permutation induced by w is πw = cr ◦ · · − ◦ c2 ◦ c1, so that qπw = q · w for every state q This defines how words map to permutations The Definition of Accessible Part The accessible part of Aacc is (R, Σ, ·R×Σ, s, F ∩ R) where R:= ∃ w ∈ Σ∗ s · w for the set of states reachable from the initial state Lemma 1 proves that this accessible part is again a permutation automaton The Definition of Final Set Transformation Fe:= ∃ q ∈ Q ∃w ∈ L(B): q · w ∈ F for the set Fe, and A/B:= (Q, Σ, ·, s, Fe) Lemma 3 proves that L(A/B) = L(A)L(B)−1 The Definition of the Spectrum Set gasc−1,PFA(m, n):= ∃Σ, ∃K, L ⊆ Σ∗, K, L accepted by permutation automata over Σ, asc(K) = m asc(L) = n asc(KL−1) = α The Definition of the Unary Interval Rauch and Holzer showed that, in the unary setting, the attainable right-quotient accepting-state complexities are exactly

1, mn: This rigid finite spectrum is what is being contrasted with the nonunary case The Definition of Minimal DFA A DFA is minimal if no equivalent DFA has fewer states Lemma 4 confirms that Aq m,α and Bq n,α are minimal permutation automata The Definition of the Final Set Size Proposition 1 states that asc(L(A)) = F for a minimal DFA A This is used to establish asc(L(A q m,α)) = m and asc(L(B q n,α)) = n The Definition of the High-Range Construction The high-range construction is group-theoretic The automaton Aq m,α acts on

k: , while Bq n,α acts on

k: × Zn+1 This structure allows for the saturation of the original final set to a full orbit The Final Result Summary Theorem 1 concludes that for all m, n ≥ 0, gasc−1,PFA(m, n) = ((if m = 0 or n = 0, N>0, if m, n ≥ 1 This resolves the larger-alphabet right-quotient case left open by Rauch and Holzer

4: The Unary Case Specifics If m = 0 or n = 0, then any languages K, L with asc(K) = m and asc(L) = n satisfy K = ∅ or L = ∅, and therefore KL−1 = ∅ This proves gasc−1,PFA(m, n) = 0 if m = 0 or n = 0 The Non-Zero Positive Range For every α ≥ m, Lemma 4 and Lemma 7 show that the witnesses Aq m,α and Bq n,α satisfy asc(L(A q m,α)) = m, asc(L(B q n,α)) = n and ascL(A q m,α)L(B q n,α)−1 = α Since mn ≥ m, the sets cover N>0 for m, n ≥ 1 This confirms gasc−1,PFA(m, n) = N>0 for m, n ≥ 1 The Phase Transition Insight Conceptually, the theorem shows that the bounded quotient spectra seen in unary permutation automata are not representative of the general case Beyond the structural impossibility of 0 for nonempty inputs, beyond that, the spectrum is complete This suggests a genuine phase transition from the unary to the nonunary setting The Group-Theoretic Core Detail The expanded proof of Lemma 5 shows that every adjacent transposition on

k − 1: is induced by a positive word over the alphabet This realization is key to showing StabSk(k) ⊆ Gn α The Final Attainability Proof The final assertion relies on the fact that every element in StabSk(k) can be realized as a permutation induced by a word in L(Bq n,α) This proves StabSk(k) ⊆ Gn α and thus the completeness of the spectrum The Unary Language Construction for Zero To prove 0 is attained, the paper introduces a unary language Ut defined by Ct:=

t + 1: , p · a ≡ p + 1 (mod t + 1) for t ≥ 1 This automaton is a permutation automaton with exactly t final states, and Proposition 1 gives asc(L(Ct)) = t The Final Spectrum Summary Theorem 1 concludes that for all m, n ≥ 0, gasc−1,PFA(m, n) = ((if m = 0 or n = 0, N>0, if m, n ≥ 1 This resolves the larger-alphabet right-quotient case left open by Rauch and Holzer

4: The Final Conclusion on Unavoidable Zero The paper concludes that beyond the structural impossibility of 0 for nonempty inputs, beyond that, the spectrum is complete This shows a genuine phase transition from the unary to the nonunary setting The Definition of Right Quotient Language

Title and authors: Tom: So we're looking at this paper called "A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata" and it’s about how accepting state complexity behaves when you move from unary alphabets to larger ones.

Jane: It looks like the authors are trying to settle a big open question that Rauch and Holzer had left hanging about what happens over arbitrary alphabets.

Tom: Right, they show that once you allow the alphabet to be nonunary, the spectrum becomes complete for right quotients when both input languages are nonempty.

Lu: It really shows that every positive integer complexity is attainable for a right quotient of two permutation automaton languages with prescribed complexities m and n over arbitrary alphabets.

Meng: So, if we're talking about something practical, it means we can hit any desired state complexity for the resulting language when we start with non-trivial input languages.

Lalam: The exact spectrum they prove is this: zero, if either input complexity m or n is zero, and all positive integers N greater than zero if both inputs are positive.

Tom: That’s a big statement. It means that zero is the only unavoidable value when you have non-empty inputs for these right quotients <ref:2605.10852#pg1,0 is the only unavoidable>.

Jane: But there's more to it, because they show that once you get past zero, the spectrum is complete, meaning every single positive integer complexity is reachable.

Tom: They do this by first proving a structural consequence about bijectivity for nonempty inputs; they show that if both input complexities m and n are greater than or equal to one, the quotient language KL minus one cannot be empty.

Jane: That sounds like a strong starting point because it basically says that for positive complexities, you’re guaranteed to get *some* result when you do this right quotient operation.

Lu: They build on that by constructing these ternary witness pairs, which are called A q m alpha and B q n alpha, where they show the input languages have exactly those required complexities m and n.

Meng: The construction involves using a group-theoretic approach for this high range part; they set up the automaton B q n alpha to act on a set that's k times Z plus one, where k is related to alpha plus one.

Lalam: This design ensures that the permutations induced on the first coordinate are exactly what you call the point stabilizer of a certain element, Stab Sk of k.

Title and authors: Tom: That stabilizer action is key because it lets them realize any element in that stabilizer group as a permutation induced by some word in B q n alpha.

Jane: So, what does that mean for someone just listening? It means the structure of the resulting quotient language isn't totally random; it’s tied to these specific group actions.

Lu: And they use this to compute the final set Fe, which is defined as being related to elements in that stabilizer group acting on a final set F.

Tom: Lemma six confirms that this final set Fe ends up being the entire range from one up to k minus one, and that directly relates back to alpha.

Jane: It seems like they are using the known results from Rauch and Holzer on unary automata—where they found the rigid interval one m times n—as a base for what happens in this more general nonunary setting <ref:2605.10852#pg1>.

Lu: Exactly. The low range of complexities is covered by those known unary witnesses, which sets up a foundation for the rest of the proof.

Tom: So, when you combine the low range coverage with this new high-range construction, they conclude that every positive integer complexity is realized for m and n greater than or equal to one.

Jane: That’s the main payoff. The paper establishes that beyond zero, there's no gap in the possible accepting state complexities for these quotients over arbitrary alphabets.

Lu: And they explicitly point out what they don't solve, which is the structural impossibility of getting zero when both input languages are nonempty.

Tom: So, to recap, the paper "A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata" shows that for non-empty inputs, zero is the only impossible complexity and all positive integers are attainable <ref:2605.10852#pg1,A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right>.

Jane: It’s a phase transition from the rigid unary setting to this complete spectrum in the nonunary case, which is pretty significant.

Lu: It suggests that the way permutations act on states in these automata opens up possibilities that weren't there when you were only restricted to unary alphabets.

Meng: From an engineering standpoint, it means if we’re designing systems where we combine two such languages, and both inputs are non-empty, we have a much wider range of acceptable performance metrics for the output language.

Title and authors: Tom: So that’s what they’re saying: the unary bound one to m times n is just one piece of the puzzle; the full picture is much richer when you move to larger alphabets <ref:2605.10852#pg1>.

Jane: It really shows how essential it was to look at this problem from a nonunary perspective, because that's where you see all these different complexities popping up.

Lu: We have to remember that their proof relies on showing every adjacent transposition on the set one through k minus one is induced by some positive word in the language B q n alpha, which is a deep result regarding the group action.

Meng: I wonder what the practical cost would be for implementing this kind of construction if you were running this at scale?

Tom: That’s a fair question, Meng. But they showed that the machinery works, and it provides that complete spectrum result for right quotients in these automata.

Jane: So for the listener, it means when you’re dealing with these types of formal systems, if you have positive complexity inputs, you can expect a wide variety of outcomes when you perform this specific quotient operation.

Lu: And they also highlight that zero is the only exception; that structural impossibility persists even in this complete setting <ref:2605.10852#pg1>.

Tom: So, to wrap up on the paper "A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata," it’s about proving completeness above zero.

Jane: It’s a big step because it shows that the unary result isn't just a special case, but rather a boundary condition for a much broader phenomenon.

Lu: And they keep emphasizing that this is about permutation automata specifically, which brings in the group action aspect as the central tool for showing everything works together.

Meng: If you had to deploy something based on this idea right now, I’d be worried about the complexity of generating those witness pairs, but theoretically it settles that part.

Tom: Theoretically, they did settle it. It’s a very clean result connecting group theory to descriptive complexity in a way that’s quite elegant for permutation automata.

Jane: So we've seen how this paper moves beyond the unary restriction to show completeness for positive complexities, while keeping zero as the only exception.

Lu: And they keep pointing out that this transition from unary to nonunary behavior is a genuine phase change in how we understand these systems.

The paper's summary: Tom: So, to wrap up that last bit, this paper is essentially showing us how accepting state complexity changes when we switch from unary alphabets to anything bigger, and it settles a big question about what numbers are even possible.

Jane: Right, so we've been talking about how some older work showed that for unary systems, the attainable complexities are just a simple interval—a range from one up to some number multiplied by another number.

Lu: But this new research tackles those arbitrary alphabets and they show that when you move to nonunary alphabets, that rigid structure breaks down completely.

Tom: The main result is this: once both of your input languages aren't empty, every single positive integer complexity becomes attainable for the right quotient operation.

Jane: So, if you have two non-empty languages, you can design them such that their resulting right quotient language has exactly any state complexity you want—one, two, three... all the way up to infinity.

Lu: They do this by building these complex group-theoretic structures and witness pairs that show how every positive number can be reached through the permutation actions induced by those languages.

Tom: It really shows that zero is the only number you can't hit when both inputs are non-empty, which was already kind of known, but this paper proves that everything else is possible.

Jane: And they call this a phase transition because it’s like moving from a very constrained system where you only see one type of outcome to one where the possibilities are truly open.

Lu: The mechanism behind that completeness comes down to how they use the point stabilizer action; every element in that stabilizer group can be realized as a permutation induced by some word in one of those languages.

Tom: That’s a deep connection between group theory and this descriptive complexity, which is pretty cool because it connects abstract math to something tangible about language processing.

Jane: So, what does this mean for someone just listening? It means if you're working with these types of systems where you combine two non-empty inputs, you have a huge range of performance metrics available for the output.

Lu: The paper highlights that the unary result is just one piece—it sets the floor for what happens, but it doesn't limit the potential above that floor when you introduce nonunary alphabets.

Tom: So we’ve covered how they proved completeness above zero, and now we can move on to looking at those specific constructions they use to build these witness pairs.

The paper's improvements: Tom: So, we've seen the main result—that above zero, every positive complexity is reachable when you move to nonunary alphabets—now let's talk about what they suggest for future work or improvements on this model.

Jane: I mean, it’s a very solid characterization of the spectrum, but are there any limitations they point out? What stops this from being a complete picture?

Lu: Well, the paper is really focused on showing that the transition from unary to nonunary isn't just a small bump; it suggests that this pattern of completeness might hold for even more complex automata structures.

Tom: Exactly. They are looking at how you can generalize this result beyond just permutation automata, which is where things get interesting for model training.

Jane: They mentioned that the core idea relies heavily on the specific properties of the stabilizer action in group theory; it’s a very specific mechanism that makes this whole thing work.

Lu: And they hint that future work could involve seeing if we can extend these group-theoretic constructions to other classes of automata, not just permutation ones.

Tom: If you can generalize this construction, you’re essentially showing that the way we represent states and transitions in these models is flexible enough to hit any complexity target.

Jane: That would have huge implications for designing new AI systems where you need precise control over the output complexity, not just a vague idea of what's possible.

Lu: And they also touch on how this completeness result contrasts with the limitations we see in simpler models, like the ones we looked at in those integer programming papers.

Tom: So, it’s about moving from deterministic bounds—like those algorithms for integer programs—to showing that for certain classes of problems, you can achieve anything you want if you have enough freedom in your input alphabet.

Jane: The implication is that complexity isn't just a fixed boundary; it’s something you can navigate by changing the underlying structure, like moving from unary to nonunary settings.

Lu: They are also exploring how this might apply to things like generative models where the state space is massive, because the group action they use handles really big sets.

Tom: It seems like the real direction here is taking these construction techniques and applying them to practical AI problems where we need to guarantee a certain level of output complexity.

Conclusion: Tom: So, to wrap up this whole discussion on "A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata," we established that above zero, every positive complexity is reachable when you move to nonunary alphabets.

Jane: It really shows that the unary restriction isn't a hard wall; it’s just one specific boundary condition for how these systems behave.

Lu: The main implication is that we can stop thinking of complexity as something strictly limited by the alphabet size, and start seeing it more as a structural property of the automaton itself.

Tom: Yeah, because they prove that once you get past zero, you’re not hitting a ceiling—you can always find a way to realize the next number up.

Jane: That means for AI designers who are looking at these quotient operations, they have much more freedom in choosing the complexity of their final output language.

Lu: They also show that this shift from unary to nonunary behavior isn't just a theoretical curiosity; it’s a genuine phase change in how we understand the underlying group actions driving these systems.

Tom: And that group theory connection is what makes this paper really interesting for machine learning engineers because it grounds the complexity in something mathematical and verifiable.

Jane: It moves us past just saying "it's possible" to showing exactly *how* it's possible through those high-range constructions they built.

Lu: And they keep pointing out that while the results are solid for permutation automata, extending this idea to more general systems is the next big research frontier.

Tom: So, we’ve seen how they proved completeness above zero for this specific model and what that means for the theoretical limits of these automata.

Jane: It’s a really neat result because it takes a known problem from older work and shows how much more room there is when you change the basic constraints.

Lu: For me, I think the real value is in seeing how this machinery might be adapted to handle the massive state spaces we see in modern generative AI architectures.

Tom: Makes sense because if you can control the complexity of a quotient language this way, it could mean controlling other aspects of the model's behavior.

Jane: Exactly, and I want to bring up that they did leave open some questions about extending these specific constructions to different types of automata next.

Lu: That’s where we should look next—seeing if those group-theoretic tools can be applied elsewhere in complexity theory.

Tom: Right, so that wraps up our time on this paper, "A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata."

Jane: It’s a solid piece of work showing how fundamental structural changes can unlock entirely new possibilities in complexity analysis.

Lu: It gives us a better map for understanding what's possible when we move away from simple unary constraints.

Tom: Thanks, Jane, Lu, Meng, and Lalam. We'll be back next time when we look at how these results might affect model training efficiency on real data.

University of California, San Diego

cs.FL

Submitted: 2026-05-11

Updated: 2026-11-10

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

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

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

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

Importance score: 89/100

The gist: A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata resolves the open larger-alphabet quotient case in accepting-state complexity theory of…

Key concepts

Permutation Automaton
A specific type of deterministic finite automaton where every input symbol causes the state transitions to be a permutation of the current set of states. This structure allows for analysis using group actions, making it suitable for studying complex language properties through algebraic methods.
Accepting-State Complexity (asc)
This measures complexity by counting the number of accepting states in a minimal DFA rather than the total number of states. The paper investigates how this complexity behaves when forming right quotients (KL-1), showing that for non-empty inputs, almost any positive integer complexity can be achieved.
Right Quotient
The right quotient operation KL-1 is defined as the set of strings 'xy' where 'y' belongs to language L and 'xy' belongs to language K. This operation is central to the study, and the paper proves that for non-empty inputs, this quotient operation yields a complete spectrum of complexities.
Unary vs. Nonunary Setting
The unary setting uses a restricted alphabet (like {a}). The paper contrasts this with the nonunary setting (arbitrary alphabets). It establishes a phase transition: the unary case is rigid with a bounded spectrum [1, mn], while the nonunary case is complete for positive complexities.

Terminology

Summary

A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata resolves the open larger-alphabet quotient case in accepting-state complexity theory of permutation automata by showing that over arbitrary alphabets, every positive acceptingstate complexity is attainable for right quotient when both input languages are nonempty

The Main Contribution

The main contribution of this paper is a complete solution of the larger-alphabet right-quotient problem left open by Rauch and Holzer [4] The authors show that once the alphabet is allowed to be nonunary, the spectrum becomes complete, meaning every positive integer occurs as the accepting-state complexity of a right quotient of two permutation-automaton languages with prescribed positive accepting-state complexities Over arbitrary alphabets, the exact spectrum is gasc−1,PFA(m, n) = (

(

if m = 0 or n = 0, N>0, if m, n ≥ 1

Structural Consequences of Non-Emptiness

The proof begins by showing a structural consequence of bijectivity for nonempty inputs First, the authors show that if m, n ≥ 1, then asc(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

Construction of the High-Range Spectrum

For every m, n ≥ 1 and every α ≥ m, a ternary witness pair (Aq m,α, Bq n,α) is constructed such that asc(L(A q m,α)) = m and asc(L(B q n,α)) = n The high-range construction is group-theoretic Specifically, the automaton Bq n,α acts on [k] × Zn+1 where k = α + 1 This design ensures that the permutations induced on the first coordinate are exactly the point stabilizer StabSk(k)

The Complete Spectrum Result

Combined with the known unary interval [1, mn], this yields the complete spectrum and resolves the larger-alphabet right-quotient case for permutation automata The final theorem states that for all m, n ≥ 0, gasc−1,PFA(m, n) = (

(

if m = 0 or n = 0,

N>0, if m, n ≥ 1

The Unavoidable Magic Value

The paper establishes that once both input languages are nonempty, every positive acceptingstate complexity is attainable for right quotient and 0 is the only unavoidable magic value This demonstrates a genuine phase transition from the unary to the nonunary setting

The Unary Case Foundation

The unary result, [1, mn], is established by Rauch and Holzer This rigidity is shown to be entirely unary, suggesting that the larger-alphabet case is not representative of the general setting

The Role of Stabilizer Actions

The mechanism behind the nonunary spectrum is characterized by the availability of a stabilizer action that expands the quotient final set across a large orbit This is demonstrated by Lemma 5, which proves that Gn α = StabSk(k)

The Low-Range Coverage

The low range is covered by the unary witnesses of Rauch and Holzer Proposition 3 confirms that for all m, n ≥ 1 and all α ∈ N, every value in the low range is realized

The Complete Spectrum Conclusion

Since mn ≥ m, the sets of values from the low range and the high range together cover all positive integers N>0 for m, n ≥ 1 Therefore gasc−1,PFA(m, n) = N>0 for m, n ≥ 1

The Zero Case Resolution

If m = 0 or n = 0, then any languages K, L with asc(K) = m and asc(L) = n satisfy K = ∅ or L = ∅, and therefore KL−1 = ∅ This proves gasc−1,PFA(m, n) = 0 if m = 0 or n = 0

The Unary Language Construction

To prove the zero case attainment, the paper introduces a unary language Ut defined by Ct:= [t + 1], p · a ≡ p + 1 (mod t + 1) for t ≥ 1 This automaton is a permutation automaton with exactly t final states, and Proposition 1 gives asc(L(Ct)) = t

The High-Range Witness Construction Details

The witness pair construction involves defining the alphabet as Σ:= (a, b, c) on [k], where a = (1 2... k), b = (1 2), and c = id[k] The transition function for Bq n,α is given by the specific rules involving addition modulo n + 1

The Minimal Quotient Automaton

Lemma 7 confirms that the quotient automaton Aq m,α/Bq n,α is minimal This minimality leads directly to the conclusion that ascL(A q m,α)L(B q n,α)−1 = k − 1 = α

The Final Theorem Statement

Theorem 1 states that for all m, n ≥ 0, gasc−1,PFA(m, n) = (

(

if m = 0 or n = 0, N>0, if m, n ≥ 1 This resolves the larger-alphabet right-quotient case left open by Rauch and Holzer [4]

The Expansion of Lemma 5 Proof

An expanded proof of Lemma 5 shows that every adjacent transposition on [k − 1] is induced by a positive word over the alphabet, which is crucial for realizing the stabilizer elements This realization allows the construction of words x ∈ L(Bq n,α) corresponding to any element in StabSk(k)

The Group-Theoretic Core

The group-theoretic core involves showing that Gn α = StabSk(k) This is achieved by demonstrating that every element in StabSk(k) can be realized as the permutation induced by a word in L(Bq n,α)

The Final Set Calculation

Lemma 6 computes the final set of the quotient automaton as Fe = [h∈Gn α h−1(FA) = [h∈StabSk(k) h−1(FA)] and concludes that Fe = (1,..., k − 1) This confirms ascL(A q m,α)L(B q n,α)−1 = α

The Unary Interval Realization

Proposition 3 confirms that for all m, n ≥ 1 and all α ∈ N, every value in the low range is realized by unary permutation automata This provides the foundation for covering the positive part of the spectrum

The Final Conclusion on Attainability

Since mn ≥ m, the sets of values from both ranges together equal N>0 for m, n ≥ 1 Therefore gasc−1,PFA(m, n) = N>0 for m, n ≥ 1 This resolves the larger-alphabet right-quotient case for permutation automata

The Unavoidable Zero Conclusion

The paper concludes that beyond the structural impossibility of 0 for nonempty inputs, the spectrum is complete This shows that right quotient for permutation automata undergoes a genuine phase transition from the unary to the nonunary setting

The Definition of Right Quotient

For languages K, L ⊆ Σ∗, the right quotient of K by L is KL−1:= ∃y ∈ L: xy ∈ K This operation is central to the study of accepting-state complexity in this context

The Definition of Accepting-State Complexity

Accepting-state complexity, asc(L), measures descriptional complexity by minimizing the number of accepting states rather than the total number of states Proposition 1 identifies this as F for a minimal DFA

The Definition of Permutation Automaton

A permutation automaton is a DFA in which, for every a ∈ Σ, the map q 7→ q ·a is a permutation of Q This property allows for the analysis using group actions

The Definition of Right Quotient Language

The language L(A/B) = L(A)L(B)−1 Lemma 3 provides the formal definition for how the quotient language relates to the original languages

The Definition of Orbit Action

If G ≤ Sn, then G acts on [n] by iπ = π(i) for i ∈ [n] and π ∈ G, and we write iG:= ∃ π∈G iπ for the corresponding orbit This notation is used to describe the action of permutation groups

The Definition of Point Stabilizer

StabG(i):= ∃ π ∈ G iπ = i for the point stabilizer of i This concept is used to characterize the structure of the induced permutations

The Definition of Induced Permutation

If w = c1c2 · · · cr, then the permutation induced by w is πw = cr ◦ · · − ◦ c2 ◦ c1, so that qπw = q · w for every state q This defines how words map to permutations

The Definition of Accessible Part

The accessible part of Aacc is (R, Σ, ·R×Σ, s, F ∩ R) where R:= ∃ w ∈ Σ∗ s · w for the set of states reachable from the initial state Lemma 1 proves that this accessible part is again a permutation automaton

The Definition of Final Set Transformation

Fe:= ∃ q ∈ Q ∃w ∈ L(B): q · w ∈ F for the set Fe, and A/B:= (Q, Σ, ·, s, Fe) Lemma 3 proves that L(A/B) = L(A)L(B)−1

The Definition of the Spectrum Set

gasc−1,PFA(m, n):= ∃Σ, ∃K, L ⊆ Σ∗, K, L accepted by permutation automata over Σ, asc(K) = m asc(L) = n asc(KL−1) = α

The Definition of the Unary Interval

Rauch and Holzer showed that, in the unary setting, the attainable right-quotient accepting-state complexities are exactly [1, mn] This rigid finite spectrum is what is being contrasted with the nonunary case

The Definition of Minimal DFA

A DFA is minimal if no equivalent DFA has fewer states Lemma 4 confirms that Aq m,α and Bq n,α are minimal permutation automata

The Definition of the Final Set Size

Proposition 1 states that asc(L(A)) = F for a minimal DFA A This is used to establish asc(L(A q m,α)) = m and asc(L(B q n,α)) = n

The Definition of the High-Range Construction

The high-range construction is group-theoretic The automaton Aq m,α acts on [k], while Bq n,α acts on [k] × Zn+1 This structure allows for the saturation of the original final set to a full orbit

The Final Result Summary

Theorem 1 concludes that for all m, n ≥ 0, gasc−1,PFA(m, n) = (

(

if m = 0 or n = 0, N>0, if m, n ≥ 1 This resolves the larger-alphabet right-quotient case left open by Rauch and Holzer [4]

The Unary Case Specifics

If m = 0 or n = 0, then any languages K, L with asc(K) = m and asc(L) = n satisfy K = ∅ or L = ∅, and therefore KL−1 = ∅ This proves gasc−1,PFA(m, n) = 0 if m = 0 or n = 0

The Non-Zero Positive Range

For every α ≥ m, Lemma 4 and Lemma 7 show that the witnesses Aq m,α and Bq n,α satisfy asc(L(A q m,α)) = m, asc(L(B q n,α)) = n and ascL(A q m,α)L(B q n,α)−1 = α Since mn ≥ m, the sets cover N>0 for m, n ≥ 1 This confirms gasc−1,PFA(m, n) = N>0 for m, n ≥ 1

The Phase Transition Insight

Conceptually, the theorem shows that the bounded quotient spectra seen in unary permutation automata are not representative of the general case Beyond the structural impossibility of 0 for nonempty inputs, beyond that, the spectrum is complete This suggests a genuine phase transition from the unary to the nonunary setting

The Group-Theoretic Core Detail

The expanded proof of Lemma 5 shows that every adjacent transposition on [k − 1] is induced by a positive word over the alphabet This realization is key to showing StabSk(k) ⊆ Gn α

The Final Attainability Proof

The final assertion relies on the fact that every element in StabSk(k) can be realized as a permutation induced by a word in L(Bq n,α) This proves StabSk(k) ⊆ Gn α and thus the completeness of the spectrum

The Unary Language Construction for Zero

To prove 0 is attained, the paper introduces a unary language Ut defined by Ct:= [t + 1], p · a ≡ p + 1 (mod t + 1) for t ≥ 1 This automaton is a permutation automaton with exactly t final states, and Proposition 1 gives asc(L(Ct)) = t

The Final Spectrum Summary

Theorem 1 concludes that for all m, n ≥ 0, gasc−1,PFA(m, n) = (

(

if m = 0 or n = 0, N>0, if m, n ≥ 1 This resolves the larger-alphabet right-quotient case left open by Rauch and Holzer [4]

The Final Conclusion on Unavoidable Zero

The paper concludes that beyond the structural impossibility of 0 for nonempty inputs, beyond that, the spectrum is complete This shows a genuine phase transition from the unary to the nonunary setting

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. Generalization of Right Quotient Complexity Analysis: The improved system can determine if a right quotient language KL-1 is empty when K and L are accepted by permutation automata with prescribed accepting-state complexities m and n, based on the structural consequence that for nonempty inputs, the quotient language cannot be empty.

  2. Spectrum Completeness Determination: The system can precisely calculate the exact spectrum of accepting-state complexity for right quotients of permutation automata over arbitrary alphabets, identifying it as g asc-1 PFA(m, n) = N>0 if m, n ≥ 1.

  3. Witness Construction and Complexity Realization: The system can construct ternary witness pairs (Aq m alpha, Bq n alpha) that demonstrate attainability of every positive integer complexity greater than or equal to m for the right quotient operation when both input languages are nonempty.

  4. Phase Transition Identification: The system can identify the genuine phase transition from the unary to the nonunary setting in right quotient for permutation automata by distinguishing between the rigid unary spectrum [1, mn] and the complete nonunary spectrum N>0 for m, n ≥ 1.

Related papers