← 研踪 PaperTrailarXiv:2512.23403 · v2
A pumping-like lemma for languages over infinite alphabets
首次提交 2025-12-29 19:49
版本更新 2026-10-28 16:46
雷达观测 2026-10-30 10:22
摘要
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.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-10-28 16:46 · 最新观测版本
A pumping-like lemma for languages over infinite alphabets
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.
查看此版本解读 →查看此版本原文 ↗