A Pumping-Like Lemma for Languages over Infinite Alphabets

arXiv (Cornell University) 2026 Preprint Open access

Read full text
Authors: Yoav Danieli
DOI: 10.4230/lipics.stacs.2026.29
Cited by: 0

Abstract

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.

Fields of Study & Subjects

Complexity and Algorithms in Graphs Advanced Graph Theory Research Polynomial and algebraic computation

Publication details

Journal / source
arXiv (Cornell University)
Publication date
1 January 2026
Language
EN
Document type
Preprint