線形有界オートマトン

コンピュータサイエンスにおいて、線形制限オートマトン（複数形はlinear bounded automata、略してLBA ）は、チューリングマシンの制限された形式です。

手術

線形制限オートマトンとは、次の 3 つの条件を満たすチューリングマシンです。

入力アルファベットには、左端と右端のマーカーとして機能する 2 つの特殊記号が含まれています。
遷移によって、エンドマーカーの上に他のシンボルが印刷されない場合があります。
その遷移は左エンドマーカーの左にも右エンドマーカーの右にも移動してはならない。^[1]^{: 225}

言い換えると、計算対象となる潜在的に無限のテープを使用する代わりに、計算は入力を含むテープ部分とエンドマーカーを保持する 2 つのテープ四角形に制限されます。

より制限の少ない別の定義は次のとおりです。

チューリングマシンと同様に、LBA は有限のアルファベットの記号を格納できるセルで構成されたテープ、テープ上の 1 つのセルに対して一度に読み取りまたは書き込みが可能で移動可能なヘッド、および有限の数の状態を備えています。
LBAは、テープが最初は無限長であるとみなされる一方で、読み取り/書き込みヘッドによってアクセスされるのは、テープの有限の連続部分のみであり、その長さは初期入力の長さの線形関数である点でチューリングマシンと異なります。そのため、線形制限オートマトンと呼ばれます。^[1]^{: 225}

この制限により、LBA は、定義が無制限のテープを前提とするチューリングマシンよりも、現実世界のコンピューターのより正確なモデルになります。

強い定義と弱い定義は、それぞれのオートマトンクラスの計算能力が同じになることにつながります。^[1]^{: 225}線形高速化定理を証明するために使用されたのと同じ議論によって。

LBA と文脈依存言語

線形制限オートマトンとは、文脈依存言語のクラスのアクセプタである。^[1]^{: 225–226}このような言語の文法に課せられる唯一の制約は、文字列をより短い文字列にマッピングする生成規則がないことである。したがって、文脈依存言語の文字列の導出には、文字列自体よりも長い文形式を含めることはできない。線形制限オートマトンとこのような文法の間には1対1の対応があるため、文字列がオートマトンによって認識されるには、元の文字列が占めるテープ以上のテープは必要ない。

歴史

1960年、ジョン・マイヒルは今日では決定性線形有界オートマトンとして知られるオートマトンモデルを発表しました。^[2] 1963年、ピーター・ランドウェーバーは決定性LBAが受け入れる言語は文脈依存型であることを証明しました。 ^[3] 1964年、S.-Y.黒田はより一般的な（非決定性）線形有界オートマトンモデルを発表し、ランドウェーバーの証明を改変して、非決定性線形有界オートマトンが受け入れる言語はまさに文脈依存型言語であることを示しました。^[4]^[5]

LBAの問題

黒田氏は、その独創的な論文の中で、後に「LBA 問題」として有名になる 2 つの研究課題についても述べています。最初の LBA 問題は、LBA によって受け入れられる言語のクラスが、決定論的 LBA によって受け入れられる言語のクラスと等しいかどうかというものです。この問題は、計算複雑性理論の言語で簡潔に次のように表現できます。

最初の LBA 問題: NSPACE (O( n )) = DSPACE (O( n )) ですか?

2 番目の LBA の問題は、LBA によって受け入れられる言語のクラスが補集合に対して閉じているかどうかです。

2番目のLBA問題: NSPACE (O( n ))= co- NSPACE (O( n ))ですか?

黒田がすでに指摘したように、2番目のLBA問題に対する否定的な答えは、最初の問題に対する否定的な答えを意味する。しかし、2番目のLBA問題には肯定的な答えがあり、それは問題提起から20年後に証明されたイマーマン・シェレプセニの定理によって示唆されている。 ^[6]^[7]今日現在、最初のLBA問題はまだ未解決のままである。サビッチの定理は、 NSPACE (O( n )) ⊆ DSPACE (O( n ² ))という最初の洞察を提供している。^[8]

参考文献

^ abcd ホップクロフト、ジョン E. ;ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。アディソン・ウェズリー。ISBN 0-201-02988-X。（印刷障害のある利用者も利用可能）
^ John Myhill (1960 年 6 月). 線形有界オートマトン (WADD テクニカルノート). ライトパターソン空軍基地、ライト航空開発部門、オハイオ州。
^ PS Landweber (1963). 「タイプ1の句構造文法に関する3つの定理」.情報と制御. 6 (2): 131–136. doi : 10.1016/s0019-9958(63)90169-4 .
^ Sige-Yuki Kuroda (1964年6月). 「言語のクラスと線形境界オートマトン」.情報制御. 7 (2): 207–223. doi : 10.1016/s0019-9958(64)90120-2 .
^ Willem JM Levelt (2008). 形式言語とオートマトン理論入門. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2。
^ イマーマン、ニール(1988)、「非決定性空間は相補性の下で閉じている」(PDF)、SIAM Journal on Computing、17 (5): 935–938、doi :10.1137/0217058、MR 0961049
^ Szelepcsényi、Róbert (1988)、「非決定性オートマトンの強制方法」、Acta Informatica、26 (3): 279–284、doi :10.1007/BF00299636、S2CID 10838178
^ アローラ、サンジーヴ、バラク、ボアズ（2009）。複雑性理論：現代的アプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4。

外部リンク

線形有界オートマトン (Forbes D. Lewis 著)
線形有界オートマトンスライド、Arthur C. Fleck 著「文脈依存言語」の一部
線形有界オートマトン、計算理論シラバスの一部、David Matuszek 著

[Hopcroft.Ullman.1979-1] ホップクロフト、ジョン E. ;ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。アディソン・ウェズリー。ISBN 0-201-02988-X。（印刷障害のある利用者も利用可能）

[2] John Myhill (1960 年 6 月). 線形有界オートマトン (WADD テクニカルノート). ライトパターソン空軍基地、ライト航空開発部門、オハイオ州。

[3] PS Landweber (1963). 「タイプ1の句構造文法に関する3つの定理」.情報と制御. 6 (2): 131–136. doi : 10.1016/s0019-9958(63)90169-4 .

[4] Sige-Yuki Kuroda (1964年6月). 「言語のクラスと線形境界オートマトン」.情報制御. 7 (2): 207–223. doi : 10.1016/s0019-9958(64)90120-2 .

[5] Willem JM Levelt (2008). 形式言語とオートマトン理論入門. John Benjamins Publishing. pp. 126–127. ISBN 978-90-272-3250-2。

[6] イマーマン、ニール(1988)、「非決定性空間は相補性の下で閉じている」(PDF)、SIAM Journal on Computing、17 (5): 935–938、doi :10.1137/0217058、MR 0961049

[7] Szelepcsényi、Róbert (1988)、「非決定性オートマトンの強制方法」、Acta Informatica、26 (3): 279–284、doi :10.1007/BF00299636、S2CID 10838178

[8] アローラ、サンジーヴ、バラク、ボアズ（2009）。複雑性理論：現代的アプローチ。ケンブリッジ大学出版局。ISBN 978-0-521-42426-4。