小石オートマトン

コンピュータサイエンスにおいて、ペブルオートマトンとは、テープ位置をマークするために使用できる有限個の「ペブル」を使用して元のモデルを拡張した オートマトンの一種です。

ペブルオートマトンが 1986 年に導入されたとき、場合によっては、ペブルを追加した決定性トランスデューサが、非決定性ログスペーストランスデューサよりも対数的なスペース節約を実現できることが示されました(つまり、非決定性マシンがテープセルを必要とする関数をテープセルで計算する)。これは、関数間にスペースを必要とするチューリングマシンにペブルを追加することを意味しています。^[1]また、ますます強力になるスタックマシンモデルの階層を、最大 3 つのペブルを持つ同等の決定性有限オートマトンに変換する構造も示され、ペブルを追加するとさらにパワーが向上することが示されました。 ${\displaystyle \log \log n}$${\displaystyle \log n}$${\displaystyle \log \log n}$${\displaystyle \log n.}$

ネストされた小石を持つツリーウォーキング オートマトンとは、固定サイズの小石を含む追加の有限集合 ( で識別される) を持つツリーウォーキング オートマトンです。通常のアクションの他に、オートマトンは現在訪問中のノードに小石を置いたり、現在訪問中のノードから小石を持ち上げて、「i 番目の小石が現在のノードに存在するか?」というテストを実行できます。小石を置いたり持ち上げたりできる順序には重要なスタック制限があります。i+1 番目の小石は、1 番目から i 番目の小石がすでにツリー上にある場合にのみ置くことができ、i+1 番目の小石は、i+2 番目から n 番目の小石がツリー上にない場合にのみ持ち上げることができます。この制限がなければ、オートマトンには決定不可能な空虚さと、通常のツリー言語を超える表現力があります。 ${\displaystyle \{1,2,\dots ,n\}}$

n 個の小石を持つ決定的 (または非決定的) ツリーウォーキング オートマトンによって認識される言語のクラスは、それぞれ(または) で表されます。また、 およびも定義します。 ${\displaystyle DPA_{n}}$${\displaystyle PA_{n}}$${\displaystyle DPA=\bigcup _{n}DPA_{n}}$${\displaystyle PA=\bigcup _{n}PA_{n}}$

• 1つの小石を持つ木歩行オートマトンによって認識されるが、通常の木歩行オートマトンでは認識されない言語が存在する。これは、これらのクラスのいずれかが比較不可能であることを意味し、これは未解決の問題である。${\displaystyle TWA\subsetneq DPA}$
• ${\displaystyle PA\subsetneq REG}$つまり、小石を追加した木歩きオートマトンが分岐オートマトンよりも弱いということである。
• 、すなわち木歩き小石オートマトンが決定論的に定義できるかどうかは不明である。${\displaystyle DPA=PA}$
• 木歩行小石オートマトンが相補性の下で閉じているかどうかは知られていない。
• ペブル階層は木歩行オートマトンに対して厳密であり、任意のnと${\displaystyle PA_{n}\subsetneq PA_{n+1}}$${\displaystyle DPA_{n}\subsetneq DPA_{n+1}}$

ツリーウォーキング ペブル オートマトンには、興味深い論理的特徴付けが可能です。^[2]推移閉包一階述語論理で記述可能なツリー プロパティの集合を で表し、肯定的推移閉包論理、つまり、否定のスコープ内で推移閉包演算子が使用されない論理についても同様とします。すると、 であり、実際、 であることが証明できます。ツリーウォーキング ペブル オートマトンによって認識される言語は、まさに肯定的推移閉包論理で表現可能な言​​語です。 ${\displaystyle FO+TC}$${\displaystyle FO+{\text{pos}}\,TC}$${\displaystyle PA\subseteq FO+TC}$${\displaystyle PA=FO+{\text{pos}}\,TC}$

• 木を歩くオートマトン
• 分岐オートマトン
• 推移閉包論理
• 小石ゲーム