Source-linked AI summary
On the equivalence between generating functions computed by memory transducers and enumerating functions produced by indexed grammars
Vincent Ghigo
TL;DR
The paper asks whether sequences computed by deterministic transducers with stacks of stacks can be represented as counting sequences of indexed-grammar objects. It constructs and relates transducer and grammar models over an arbitrary structure A, proving equivalence and applying it to polynomial recurrences over N.
Problem
The paper addresses counting and representation problems for indexed-grammar trees and sequences computed by transducers over a structure A.
Method
The paper develops transformations between A-indexed grammars and memory transducers, using intermediate grammar and transducer constructions to establish their correspondence.
Results
The paper proves that functions computed by Pk+2(A)-transducers are equivalent to functions enumerating trees generated by Pk(A)-grammars, including the P2(A) and A-grammar case.
Takeaways & Limitations
For N with decrement and the non-zero predicate, sequences defined by polynomial recurrences can be represented by context-free grammars with indexes in N.
Takeaways & Limitations
The constructions rely on assumptions including determinism, completeness, and the absence of livelocks in the relevant transducers.
Abstract
from arXiv · showhide
We consider the sequences of natural integers that can be computed by a deterministic transducer, with input in a structure A, output in N. and with memory the set of stacks of stacks of A. We show that these sequences are, exactly, the counting sequences of formal languages generated by unambiguous context-free indexed grammars (equivalently, the counting sequences of derivation trees of arbitrary context-free indexed grammars), with indexes in A. This general theorem applies, notably, to the set of natural integers endowed with the operation -1 and the non-zero predicate, showing that the polynomial recurrences count exactly the index-languages (where the parameter used for counting is the index itself).
1 Introduction
The paper studies counting and representation problems for combinatorial sequences over an arbitrary structure A. It relates deterministic transducers with stacks of stacks to indexed grammars whose indexes come from A.
- The counting problem asks how many objects in a family E(n) correspond to each integer n, and how those numbers can be computed.
- The representation problem asks whether a sequence computed by a recurrence or transducer can be realized as counts of combinatorial objects.
- The paper studies these questions for trees generated by indexed grammars and sequences computed by deterministic transducers over A.
- A transducer with memory over A is an automaton whose initial memory is supplied as input, while an A-indexed grammar attaches A-elements to nonterminals and permits guarded operations on indexes.
- The framework extends the representation result to transducers whose memory is the set of k-stacks over A for every k ≥2.
2 Preliminaries
The preliminaries define structures, stacks, memory transducers, indexed grammars, and the run and derivation objects used to connect them. Stack operations and predicates act on the topmost atom, while symbolic runs abstract away unobserved stack suffixes.
- A structure A consists of a set S, predicates on S, and operations mapping elements of S to elements of S.
- A stack over A is a sequence of indexed symbols, with predicates and operations inherited from A and evaluated on its topmost atom.
- Nested stacks are ordered by level, with the outermost stack having order 1; Pk(A) denotes order-k stacks over A.
- An A-transducer is an automaton with finite states, guarded transitions, stack operations, an initial configuration, and an accepting configuration.
- An indexed grammar applies guarded rules to indexed nonterminals, transforming their indexes through operations of A and generating derivation trees from an axiom.
- Symbolic runs represent sets of runs sharing transitions by replacing an unobserved stack suffix with a bottom marker, enabling correspondence with grammar derivation trees.
3 From indexed grammar to memory transducer
This section proves that every suitable A-indexed grammar can be simulated by a P2(A)-transducer. The construction uses normal-form grammar rules and an order-2 stack to encode derivation trees and their nondeterministic choices.
- Theorem 1 states that an A-indexed grammar without infinite derivations has a P2(A)-transducer computing its number of derivation trees for each input index.
- Grammar normal form: The grammar is converted to a normal form separating terminal production, nonterminal production, and operations on indexes.
- Grammar normal form: Normal-form rules include index operations, conjunction, nondeterministic choice, and terminal dumping, with complementary guards added for each rule.
- Computing transducer: The transducer T1(G) simulates each derivation tree with an order-2 stack and encodes nondeterminism through push1 operations.
- Computing transducer: The proof uses structural induction to show that the transducer outputs a^i exactly when the grammar has i corresponding leftmost derivations.
4 From memory transducer to index grammar
This section transforms a deterministic memory transducer into an indexed grammar whose derivation trees enumerate the transducer’s computed function. The construction proceeds through predicate-augmented transducers, alternating transducers, and proof grammars, while preserving correspondence between accepting computations and derivation trees.
- Theorem 3: Theorem 3 states that an A-indexed grammar produces exactly u(σ) derivation trees from the axiom indexed by σ, for every σ ∈ S_A.The construction therefore converts the transducer’s computed values into derivation-tree counts.
- Predicate-augmented transducer: A predicate-augmented P(A)-transducer is constructed to produce u(σ) runs from X[σ], using predicates that identify productive pop1 operations.The auxiliary transducer T2(A) simulates the order-2 stack affected by each pop1 operation and rejects unproductive operations.
- Predicate-augmented grammar: A grammar with additional predicates produces u(σ) derivation trees from S[σ], replacing the predicate-augmented transducer’s accepting runs with grammar trees.The proof uses an explicit transformation T3 and establishes surjective and injective correspondences between well-formed runs and derivation trees rooted in S.
- Proof grammar: The proof grammar uses non-terminals containing the current state, symbol, guessed post-pop state, and a memory of state pairs satisfying the predicates on the simulated stack.These memories are computed incrementally and then used in rules simulating push1 operations.
- Uniqueness conditions: Determinism, completeness, and absence of livelocks ensure that the possible memory values of non-terminals form a total function.The alternating-transducer stage also relies on a uniqueness property to guarantee at most one relevant accepting continuation.
5 Conclusions and further work
The paper establishes equivalences between transducer-computed functions and functions enumerating trees generated by indexed grammars, including a hierarchy for k-stacks. It also applies the result to polynomial recurrences and identifies a potential route toward representation results for D-finite series.
- Conclusions: P_k+2(A)-transducers and functions enumerating trees generated by P_k(A)-grammars define equivalent classes of functions.The equivalence is stated for the structure A and all relevant stack orders.
- Conclusions: For A=N with operation n 7→n−1 and the non-zero predicate, polynomially recurrent sequences can be represented by context-free grammars with indexes in N.This follows because such sequences are computed by deterministic transducers with stacks of stacks of N.
- Further work: The transducer–grammar correspondence extends established links between N-linear recurrences and regular grammars and between N-algebraic recurrences and context-free grammars.The paper presents this link as an extension to indexed grammars and related transducer models.
- Further work: The framework could help identify syntactic restrictions on indexed grammars relevant to the representation problem for D-finite series.The passage presents this as a possible use because indexed grammars are contained in series defined by polynomial recurrences.
A.1 Section 3.1 proof
The proof introduces a normal-form transformation for A-grammars that preserves the number of □-free derivation trees. It decomposes the construction into transformations enforcing rule forms, unique rules per non-terminal, and complementary rules.
- Proof strategy: Lemma 16 asserts a transformation from an A-grammar to normal form that preserves the number of □-free derivation trees from S[σ].The preservation claim applies to each index σ in S_A.
- Proof strategy: The construction uses separate transformations to enforce the required rule form and the only-one-rule-per-non-terminal condition.Complementary rules are added after these two transformations.
A.1.0.1 First transformation
The first transformation Tsep converts an A-grammar into the required rule forms while preserving the number of derivation trees rooted at the original start symbol. Its correctness is established through mutually total mappings between corresponding derivation trees.
- First transformation: Tsep transforms an A-grammar into a grammar satisfying the required rule forms.The construction handles terminals that infringe the properties by adding a rule using the bottom marker and identity operation.
- Preservation: Lemma 18 states that if G produces u(σ) derivation trees from S[σ], then Tsep(G) produces u(σ) derivation trees rooted in S[σ].Thus, the transformation preserves the counted derivation trees at the start symbol.
- Correctness proof: The proof constructs a correspondence between derivation trees of G and transformed trees rooted in original non-terminals.The correspondence is shown by promoting Tsep in both directions and proving the resulting mappings total.
- Correctness proof: For each transformed rule, the existence of the associated rule sequence is equivalent to the existence of the original rule in G.This equivalence supports unique reconstruction during the reverse mapping.
A.1.0.2 Second transformation
The second transformation T1rule modifies the grammar produced by Tsep to satisfy the only-one-rule-per-non-terminal property. Lemma 20 shows that it preserves the number of derivation trees from the start symbol through a bijective correspondence.
- Second transformation: T1rule is applied to the grammar obtained from Tsep to enforce the only-one-rule-per-non-terminal property.The transformation is introduced as the next step after Tsep.
- Preservation: Lemma 20 states that T1rule(Tsep(G)) produces u(σ) derivation trees rooted in S[σ] whenever G does.The result preserves the derivation-tree count after both transformations.
- Correctness proof: The proof relates derivation trees of Gsep to transformed trees rooted in indexed non-terminals through promoted mappings.The mappings are proved total by structural induction.
- Correctness proof: Non-terminals introduced by Tsep have one rule and therefore require no further transformation under T1rule.This makes the induction immediate for trees rooted in those added non-terminals.
- Correctness proof: For an original non-terminal, the transformed rule exists exactly when the source grammar has the corresponding number of rules.The induction then gives a uniquely determined preimage derivation tree.
A.2 Theorem 1 proof
The proof establishes that the deterministic transducer’s output equals the number of leftmost derivations generated by the indexed grammar. It verifies this correspondence by considering the unique applicable rule and matching each grammar rule type with transducer behavior.
- Inductive correspondence: The transducer output tT1(G)(X1[u#2]) equals the number #LmDG(u) of leftmost derivations for every u.This equality is proved by induction over u and the corresponding transducer runs.
- Inductive correspondence: Normal form ensures that only one rule applies to the leftmost letter of u.Determinism then allows the proof to analyze the unique applicable grammar rule case by case.
- Rule cases: Complementary rules contribute zero derivations, and the transducer correspondingly produces output zero.The complementary guard prevents an accepting run in both representations.
- Rule cases: Dumping and operation rules preserve the inductive count through the corresponding pop2 or operation transitions.In each case, the transducer reaches the continuation whose output is the inductively established grammar count.
- Rule cases: AND rules preserve the count by passing control to the transformed continuation with the corresponding pushed symbols.The transducer uses a push2 operation encoding the grammar’s AND expansion.
- Base case: For an empty production, both the grammar and transducer contribute exactly one derivation or accepting run.The base case follows from the unique rule acting on #2.
A.3 proof of Section 4.1
This section proves that any P2(A)-transducer can be transformed into normal form without changing the function it computes. The construction uses three deterministic rule transformations that impose progressively stronger structural restrictions.
- Main result: Lemma 21 states that every P2(A)-transducer can be transformed into normal form while preserving its computed function.The normal-form transformation is the central claim of this section.
- Transformation stages: The transformation first restricts push operations to unary and binary forms.Higher-arity pushes are decomposed into simpler operations.
- Transformation stages: The second transformation ensures that only pop1 rules produce output while retaining the unary and binary push restrictions.This separates output production from other transition types.
- Transformation stages: The final transformation enforces a single order-1 symbol while preserving the earlier structural properties.The three stages are cumulative rather than independent restrictions.
- Initial normalization: A draining state ensures that pop1 is applied only when the topmost order-2 symbol is #2.The construction repeatedly performs pop2 transitions until #2 is reached.
A.3.0.1 First transformation
The section constructs successive transducer transformations that preserve the computed function while enforcing normal-form properties. It decomposes pushes, delays output to pop1, and encodes runs so the resulting machines retain determinism and equivalent behavior.
- First transformation: Tbin decomposes every n-ary push_i operation with n > 2 into unary and binary push_i operations.The construction introduces intermediate states and symbols to simulate the original push.
- First transformation: Lemma 23 states that Tbin(A) computes the same function u(σ) as A.The proof establishes a bijection between symbolic well-formed runs of A and Tbin(A).
- First transformation: Uniqueness of intermediate states makes the push decomposition deterministic.Structural induction shows that both the forward transformation and its inverse are total functions on the relevant runs.
- Second transformation: Tprod transforms Tbin(A) so that output production is delayed until a pop1 transition while unary and binary push properties are preserved.The delay is deterministic and finite, so it preserves runs and the computed function.
- Second transformation: Lemma 25 states that Tprod(Tbin(A)) remains a P2(A)-transducer computing u(σ).The construction preserves the function while changing when output is produced.
- Third transformation: T1symb further enforces the single-order-1-symbol property while preserving the earlier push and pop1 output restrictions.Its correctness is stated in Lemma 27 for T1symb(Tprod(Tbin(A))).