Score: 0
A pumping-like lemma for languages over infinite alphabets
Published: December 29, 2025 |
arXiv ID: 2512.23403v1
By: Yoav Danieli
We prove a kind of a pumping lemma for languages accepted by one-register alternating finite-memory automata. As a corollary, we obtain that the set of lengths of words in such languages is semi-linear.
Similar Papers
86%
Word equations and the exponent of periodicity
Formal Languages and Automata Theory
Finds patterns in word puzzles with rules.
11 Nov 2025
0
85%
Pumping-Like Results for Copyless Cost Register Automata and Polynomially Ambiguous Weighted Automata
Formal Languages and Automata Theory
Makes computers understand complex math patterns.
11 Feb 2025
0
85%
An algebraic theory of ω-regular languages, via μν-expressions
Logic
Makes computer checks for infinite loops work.
15 May 2025
0
Category
Computer Science:
Formal Languages and Automata Theory