木を歩くオートマトン

ツリーウォーキングオートマトン（TWA）は、文字列ではなくツリー構造を扱う有限オートマトンの一種です。この概念はもともとAhoとUllmanによって提案されました。^[1]

以下の記事では、ツリーウォーキングオートマトンについて扱います。通常のツリー言語に密接に関連するツリーオートマトンとは異なる概念については、分岐オートマトンを参照してください。

すべてのツリーはバイナリであると想定され、固定アルファベット Σ のラベルが付けられます。

非公式には、ツリーウォーキング オートマトン (TWA) A は、入力ツリーを順番に歩く有限状態デバイスです。各瞬間に、 A は状態qのノードv を訪れます。状態q、ノードvのラベル、およびノー​​ドがルート、左の子、右の子、またはリーフのいずれであるかに応じて、A は状態をqからq'に変更し、 vの親またはその左または右の子に移動します。TWA は、ツリーが受け入れ状態に入ると受け入れ、拒否状態に入るか無限ループになると拒否します。文字列オートマトンと同様に、TWA は決定的または非決定的になります。

より正式には、アルファベット Σ 上の (非決定性) ツリーウォーキングオートマトンとは、組 A = ( Q、 Σ、I、F、R、 δ)です。 ここで、Q は状態の有限集合、その部分集合I、F、およびR は、それぞれ初期状態、受け入れ状態、および拒否状態の集合であり、δ ⊆ ( Q × { root、left、right、leaf } × Σ × { up、left、right } × Q)は遷移関係です。

ツリーウォーキング オートマトン の簡単な例としては、入力ツリーに対して深さ優先探索(DFS) を実行する TWA があります。このオートマトンには 3 つの状態、 があります。は状態のルートから始まり、左のサブツリーに進みます。次に、ツリーを再帰的に処理します。 が状態のノードに入るときは常に、 の左のサブツリーが処理されたばかりであることを意味し、 の右のサブツリーに進みます。 が状態のノードに入る場合は、ルートを含むサブツリー全体が処理されたことを意味し、の親まで移動し、 が左の子であるか右の子であるかに応じて、状態をまたはに変更します。 ${\displaystyle A}$${\displaystyle Q=\{q_{0},q_{\mathit {left}},q_{\mathit {right}}\}}$${\displaystyle A}$${\displaystyle q_{0}}$${\displaystyle A}$${\displaystyle v}$${\displaystyle q_{\mathit {left}}}$${\displaystyle v}$${\displaystyle v}$${\displaystyle A}$${\displaystyle v}$${\displaystyle q_{\mathit {right}}}$${\displaystyle v}$${\displaystyle A}$${\displaystyle v}$${\displaystyle q_{\mathit {left}}}$${\displaystyle q_{\mathit {right}}}$${\displaystyle v}$

分岐オートマトンとは異なり、ツリーウォーキングオートマトンは分析が難しく、単純な特性でさえ証明するのは簡単ではありません。次のリストは、TWA に関連するいくつかの既知の事実をまとめたものです。

• BojańczykとColcombet ^[2]が示し​​たように、決定論的TWAは非決定論的TWAよりも厳密に弱い（）${\displaystyle {\mathit {DTWA}}\subsetneq {\mathit {TWA}}}$
• 決定論的TWAは相補性の下で閉じている（しかし非決定論的TWAでも同じことが成り立つかどうかは分かっていない^[3]）
• TWAによって認識される言語の集合は正規木言語（）に厳密に含まれており、つまり、どの木歩行オートマトンでも認識されない正規言語が存在する（BojańczykとColcombetを参照）。^[4]${\displaystyle {\mathit {TWA}}\subsetneq {\mathit {REG}}}$

• ペブルオートマトン、ツリーウォーキングオートマトンの拡張

• Mikołaj Bojańczyk: 木を歩くオートマトン。簡単なアンケート。