A pumping-like lemma for languages over infinite alphabets

arXiv:2512.23403 · cs.FL · Submitted 2025-12-29 · Read on arXiv

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