A pumping-like lemma for languages over infinite alphabets
cs.FL
Submitted: 2025-12-29
Updated: 2026-10-28
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
The gist: We prove a pumping-like lemma for languages accepted by one-register alternating finite-memory automata over an infinite alphabet.
Terminology
Abstract
We prove a pumping-like lemma for languages accepted by one-register alternating finite-memory automata over an infinite alphabet. Every sufficiently long accepted word has a nonempty factor in a bounded suffix that can be repeated under successive powers of a single alphabet permutation. The proof analyzes accepting runs backwards, counting register values by their state profiles within the remaining suffix and summarizing values outside it. We derive effective semi-linearity of the sets of accepted word lengths and prove non-closure under reversal, concatenation, and Kleene star. We also show that this pumping lemma cannot be extended to alternating automata with two registers.
Related papers
- Quantitative Verification of Infinite-State Networks
- A Unary-to-Nonunary Transition in the Accepting-State Spectrum of Right Quotient for Permutation Automata
- Positive-Data Learning of Fixed-Observation Linear MCFGs from Working Binary Presentations
- On the Separability Problem of VASS Reachability Languages
- Exact Accepting-State Spectrum for Reversal of Permutation Automata
- An exact compress-with-another threshold in a binary automaton family