无限字母表语言的泵引引理

本文探讨了理论计算机科学中的一个基本问题：如何表征特定类型自动机（特别是那些在无限字母表上运行的自动机）接受的语言的结构。泵引引理是证明一种语言不是正则语言的关键工具。这项工作将这一概念扩展到更复杂的模型（单寄存器交替有限内存自动机），为分析此设置中语言的复杂性提供了新工具。单词长度集合是半线性的结果非常重要，因为它为可能的语言提供了结构约束。

• •将泵引引理扩展到无限字母表上的语言。
• •侧重于单寄存器交替有限内存自动机接受的语言。
• •表明此类语言中单词长度的集合是半线性的。