無限アルファベット上の言語に対するポンピング補題

この論文は、理論計算機科学における基本的な問題、つまり、特定の種類のオートマトン、具体的には無限アルファベット上で動作するオートマトンの受け入れる言語の構造をどのように特徴付けるかという問題に取り組んでいます。ポンピング補題は、言語が正則でないことを証明するための重要なツールです。この研究は、この概念をより複雑なモデル（1レジスタ交互有限メモリオートマトン）に拡張し、この設定における言語の複雑さを分析するための新しいツールを提供します。単語の長さの集合が準線形であるという結果は、可能な言語に対する構造的制約を提供するという点で重要です。

• •無限アルファベット上の言語へのポンピング補題の拡張。
• •1レジスタ交互有限メモリオートマトンによって受け入れられる言語に焦点を当てる。
• •そのような言語における単語の長さの集合が準線形であることを示す。