Pumping Constants for Infinite Alphabets

1 Introduction

• Finite-memory automata use registers to store and compare previously seen letters, defining quasi-regular languages over infinite alphabets.They can copy input letters to registers, but their comparisons and copying are restricted to register contents and input letters.Source: §1 · p. 1
• The pumping lemma is a key tool for showing non-regularity, but a two-register automaton provides a counterexample to its direct extension to quasi-regular languages.The open question was whether a similar counterexample exists for one-register automata.Source: §1 · pp. 1–2
• Pumping length and permutation order trade off: longer pumping lengths reduce the required order to two for general automata and to one for one-register and hierarchical automata.Every one-register automaton satisfies the classical pumping lemma, with a quadratic pumping-length upper bound that is optimal up to constant factors.Source: §1 · pp. 2–3
• For multi-register automata, pumpability for given constants and classical pumpability are undecidable, whereas minimal classical pumping length is computable for non-guessing one-register automata.The paper therefore does not provide a general algorithm for computing optimal pumping constants.Source: §1 · p. 2
• For general finite-memory automata, the paper improves permutation-order bounds from (2r)! to bounds governed by Landau’s function and shows that order two suffices with a sufficiently larger pumping length.The earlier bound at pumping length equal to the number of states was (2r)! [5, Theorem 7].Source: §1 · pp. 2–3

2 Finite-memory automata

• Registers retain previously seen alphabet symbols, while transitions compare input with register contents and copy input symbols into registers.The accepted languages are called quasi-regular.Source: §2 · p. 4
• A one-register automaton recognizes words in which some letter appears more than once.This language is denoted L_eq.Source: §2 · p. 4
• Automaton C imposes overlapping equality constraints, and its language fails the stated pumping lemma for every pumping length p.Source: §2 · p. 6

3 Pumping lemmas for finite-memory automata

• The generalized pumping condition allows a finite-order alphabet permutation and is parameterized by input length p and permutation-order bound d.The classical pumping lemma is the special case d = 1.Source: §3 · p. 6

3.1 Number of states as input length

• Finite-memory automata with n states and r registers have an (n,g(r))-pumping bound for r ≥ 7, and the order bound is worst-case optimal.The lower-bound construction rules out every d < g(r) for an automaton with n = r + 1 states and r registers.Source: §3.1 · pp. 7, 9

3.2 Input lengths with small permutation orders

• For every r ≥ 1, every language accepted by a finite-memory automaton with n states and r registers is (3(r2!)n, 2)-pumpable.For sufficiently long words, there are indices 1 ≤ i < j ≤ N and a D-permutation α of order at most 2 such that α(θᵢ) = θⱼ.Source: §3.2 · p. 9

3.3 Minimal pumping constants

• Deciding (p,d)-pumpability, pumpability for some d at a given p, or whether the classical pumping lemma holds is undecidable for finite-memory automata.Source: §3.3 · p. 10

4 Pumping lemma for one-register automata

• One-register automata satisfy the classical pumping lemma: every language is (11n^2+n,1)-pumpable for an automaton with n states.The proof pumps either when an accepting run repeats a configuration or when it contains compatible register-updating transitions.Source: §4 · pp. 10–12

4.1 Minimal pumping length

• For one-register automata, the quadratic pumping bound is necessary up to constant factors: a family of description size O(n) has minimal classical pumping length Ω(n^2).The example’s automata have 4n+2 states, while a word of length n^2+5n cannot be pumped.Source: §4.1 · pp. 12, 14

4.2 Computing minimal pumping lengths

• The minimal classical pumping length is computable for non-guessing one-register automata, whose pumping length is bounded above by 3n^2+n.The procedure searches candidate lengths up to that bound and decides pumpability by checking finitely many bounded-length representatives up to D-permutations.Source: §4.2 · pp. 14–15

4.3 Extension to other models

• Hierarchical finite-memory automata with n states and r registers satisfy the classical pumping lemma with bound ((11n+1)rn,1).Source: §4.3 · p. 16
• Two compatible transitions yield a straightforward pumping, so it suffices to show that every run either repeats a configuration or contains such a pair.The proof establishes this alternative by examining a sufficiently long prefix of an accepting run.Source: §4.3 · p. 16
• Starting with the first (11n+1)^r n transitions, the proof partitions runs by updates at successive register levels, preserving earlier registers and obtaining a sub-run of at least (11n+1)n transitions.If there are at most 11n updates at a level, one of the resulting at most 11n+1 sub-runs is long enough to continue the argument at the next level.Source: §4.3 · p. 17
• After the first r−1 registers are preserved, either n consecutive transitions preserve all registers, giving repeating configurations, or 11n+1 updates at level r yield a compatible pair.The resulting sub-run has at least (11n+1)n = 11n^2+n transitions.Source: §4.3 · p. 17

• For general finite-memory automata, the paper improves known permutation-order bounds and shows order two suffices when the pumping length is sufficiently long.Source: §5 · p. 17
• One-register and hierarchical register automata satisfy the classical pumping lemma without any nontrivial alphabet permutation.Source: §5 · p. 17
• In the one-register case, the quadratic upper bound on pumping length is optimal up to constant factors.Source: §5 · p. 17
• Optimal pumping constants cannot be computed in general, motivating the search for subclasses beyond non-guessing one-register automata with decidable optimal or near-optimal constants.Source: §5 · p. 17
• Whether the order-two pumping length for general finite-memory automata can be substantially reduced from its current Ramsey-type bound remains open.Source: §5 · p. 17