Source-linked AI summary
Construction of a DFA for Computing Grundy Numbers in the Successful Derivation Games on Right-Linear Grammars
Yoshiaki Takata, Yusuke Inoue, Hiroyuki Seki
TL;DR
The least upper bound of Grundy numbers is undecidable for successful derivation games on general linear CFGs. This paper constructs DFAs for Grundy-number computation on RLGs, establishes regularity and decidability, and proves PSPACE-completeness for the least-upper-bound problem.
Problem
The least upper bound of Grundy numbers in the successful derivation game is undecidable in general even for linear CFGs.
Method
The paper constructs a DFA that computes the Grundy number of a position in the successful derivation game on a right-linear grammar.
Results
The set of RLG positions with any given Grundy number is regular, and computing the least upper bound of Grundy numbers is PSPACE-complete.
Takeaways & Limitations
For successful derivation games on RLGs, Grundy-number classification is regular and the least-upper-bound question is decidable.
Takeaways & Limitations
The game assumes CFGs have no cycle of unit rules so that derivations have finite length and the game is loop-free.
Abstract
from arXiv · showhide
Inoue et al. have introduced the successful derivation game (SDG) on context-free grammars (CFGs), which is a generalization of classic heap-based games including subtraction games and Keyles, and shown that the least upper bound of the Grundy numbers in the SDG on a given CFG G is undecidable in general even when we restrict G to be a linear CFG. This paper shows that for the SDG on a right-linear grammar (RLG), we can construct a DFA for computing the Grundy number of a given position. In other words, for the SDG on an RLG, the set of positions with a given Grundy number c is regular. As a corollary, the least upper bound of the Grundy numbers in the SDG on a given RLG is decidable. We also investigate the complexity of computing the least upper bound of the Grundy numbers in the SDG on a given RLG, and it is shown to be PSPACE-complete.
1 Introduction
The paper addresses Grundy-number computation in successful derivation games, where general linear CFGs retain undecidability, by exploiting right-linear grammars. It constructs DFAs for fixed Grundy numbers and establishes decidability and PSPACE-completeness results.
- Successful derivation games generalize a subclass of heap-based games, including subtraction games and Keyles.
- The least upper bound of Grundy numbers is undecidable for successful derivation games on CFGs, even when grammars are linear.
- For right-linear grammars, the paper constructs a DFA that computes the Grundy number of a given position.
- The paper shows that computing the least upper bound of Grundy numbers for right-linear grammars is PSPACE-complete.
- The paper outlines definitions, DFA construction and correctness, PSPACE-completeness, examples, and a conclusion.
2 Definitions
This section defines CFGs, derivation games, positions, legal moves, Grundy numbers, and the grammar conditions used to ensure finite play. It also recalls prior computability, boundedness, and undecidability results.
- A CFG is a tuple of nonterminals, terminals, production rules, and an initial symbol, with derivations constrained to rules in the grammar.
- A grammar is linear when each rule has at most one nonterminal on its right-hand side, and right-linear when rules have terminal strings or terminal strings followed by one nonterminal.
- The successful derivation game starts from {(I, w)}, replaces a chosen pair using a compatible production, and ends when a player has no legal move.
- The Grundy number is a nonnegative integer defined using the minimum excluded value of successor Grundy numbers, with zero for positions having no successor.
- Because unit-rule cycles are excluded, the game is loop-free and Grundy numbers are well-defined; prior work established polynomial computability and boundedness but undecidability of the least upper bound for linear CFGs.
- In the colored-stone subtraction-game example, moves remove one a, two a’s, or one b from left to right, producing illustrative Grundy values.
3 DFA Representing the Set of Positions With a Given Grundy Number
For each nonterminal and candidate Grundy number, the paper constructs a DFA that reads words right to left while tracking Grundy values of suffix-related positions. DFA emptiness then determines the maximum Grundy number.
- For each nonterminal A and i ≤ m_A, the construction produces a DFA M_A,i, with m_A an upper bound on possible Grundy numbers.
- The maximum Grundy number is found by checking which languages L(M_A,i) are nonempty and which higher-index languages are empty.
- All M_A,i share their state set, start state, and transition function, differing only in their final states.
- Construction of M_A,i: The DFA reads words from right to left and stores Grundy numbers for positions associated with every nonterminal and suffix of the input.
- Construction steps: The grammar rules are divided into unit, terminal, and nonterminal-containing classes, with unit rules ordered topologically because they are acyclic.
- Construction of M_A,i: During a transition, successor Grundy numbers are computed from the current state and rules, then combined into the next state; final states identify the target Grundy number.
4 Correctness of the Construction of DFAs
The correctness proof shows that the constructed DFAs track Grundy numbers of suffix-related successor positions while reading words in reverse. Consequently, accepted words characterize positions with each Grundy number, making the relevant position sets regular and the maximum-Grundy problem decidable.
- Construction invariant: The DFA state records Grundy numbers for nonterminals and suffixes while reading a word from right to left.This supports the correspondence between automaton states and successor-position Grundy values.
- Supporting lemma: Lemma 1 preserves the automaton invariant by relating a state containing xBj to a shorter-prefix state containing Bj.The equivalence is proved by repeatedly expanding the transition relation.
- Correctness proof: The proof establishes by induction that Ai is reached after reading w exactly when GG,A(wR) = i.The outer induction handles word length, while the inner induction orders nonterminals according to <Γ.
- Correctness proof: The key inductive identity is JA,q,a = {GG(s) | s ∈ S}, so the position's Grundy number equals mex(JA,q,a).Here S is the set of successor positions of {(A, wR)}.
- Consequences: For every A and c ≤ mA, the language of words with GG,A(w) = c is regular.The result follows from the DFA characterization and closure of regular languages under reversal.
- Consequences: Max-Grundy-Number-in-SDG is decidable for right-linear grammars by checking DFA-language emptiness for the target and larger Grundy values.The procedure checks L(MA,k) ≠ ∅ and L(MA,i) = ∅ for every k < i ≤ mA.
5 PSPACE-Completeness of Max-Grundy-Number-in-SDG on RLGs
The paper proves PSPACE-completeness for computing the maximum Grundy number in SDGs restricted to right-linear grammars. Membership follows from polynomial-space DFA reachability, while hardness is obtained by reduction from regular-grammar non-universality.
- PSPACE membership: Max-Grundy-Number-in-SDG for right-linear grammars is in PSPACE.The proof reduces the problem to deciding nonemptiness of languages recognized by the constructed DFAs.
- Conclusion: Therefore, Max-Grundy-Number-in-SDG on right-linear grammars is PSPACE-complete.This combines the membership lemma with the reduction-based hardness proof.
- PSPACE membership: A nondeterministic polynomial-space algorithm guesses DFA transitions and accepts upon reaching a final state within |Q| steps.Each state and the binary step counter require polynomial space because the state representation and |Γ′| + |ΓN| are polynomially bounded.
- PSPACE hardness: The problem is PSPACE-hard via a polynomial-time reduction from Regular-Grammar-Non-Universality.The source problem asks whether a regular grammar fails to generate all words in Σ+.
- PSPACE hardness: The hardness reduction remains valid for regular grammars without ε-rules, since ε-membership and ε-rule elimination are polynomial-time operations.Right-linear grammars are used as the target grammar class for the reduction.
I3 I4 I5 I6 IALL
The reduction uses auxiliary nonterminals whose Grundy values encode whether a word belongs to the original regular grammar. In particular, I3 distinguishes membership from non-membership through a binary Grundy-value outcome.
- Auxiliary nonterminals: For every w ∈ Σ+, GG′,I5(w) > 0, which implies GG′,I4(w) = 0 and GG′,I3(w) = 1.The positivity of I5 follows from the complementary zero-value behavior of I6 and IALL.
6 Examples
Examples 2 and 3 instantiate the DFA construction for right-linear grammars and verify that the resulting automata classify positions by Grundy number.
- Example 2: Example 2 applies the construction to a grammar with one nonterminal and m_A = 3, producing DFAs M_A,i for i ≤ 3.The grammar has alphabet {a, b} and rules A → aA | aaA | bA | a | aa | b.
- Example 2: The constructed DFA satisfies w ∈ L(M_A,i) if and only if GG,A(w^R) = i for the tested words.The behavior was simulated on words of length at most 4.
- Example 2: The examples identify languages L(M_A,0) and L(M_A,1), and display both a minimum equivalent DFA and a DFA recognizing L(M_A,0)^R.These automata are shown in Figures 4 and 5.
- Example 3: Example 3 extends the construction to a grammar with nonterminals A and B, using m_A = 4 and m_B = 2.Its rules include A → aA | aaA | B | a | aa and B → bA | b.
- Example 3: For Example 3, the construction partitions rules into nonterminal, unit, and terminal-related sets, orders nonterminals, and restricts the DFA to states reachable from q0.The transition components are defined in that order; because every B-rule starts with b, J_B,q,a is empty.
- Example 3: The partial game graph confirms w^R ∈ L(M_X,i) if and only if GG,X(w) = i, while the resulting DFA languages are listed for the example.Figure 6 shows the constructed DFA, and Figure 8 shows the minimum DFA equivalent to M_A,0.
7 Conclusion
The paper establishes regular-language and complexity results for successful derivation games on right-linear grammars.
- Conclusion: A DFA can compute the Grundy number of each position in the successful derivation game on a right-linear grammar.Equivalently, positions with any fixed Grundy number c form a regular set.
- Conclusion: The least upper bound of Grundy numbers is decidable for an SDG on a right-linear grammar, unlike the general linear-CFG case.For linear CFGs, this quantity is known to be undecidable in general.
- Conclusion: Computing the least upper bound of Grundy numbers for an SDG on an RLG is PSPACE-complete.