ツリー（オートマトン理論）

オートマトン理論では、ツリーはツリー構造を自然数のシーケンスとして 表現する特定の方法です。

例えば、木の各ノードは自然数集合上の単語( )であり、この定義をオートマトン理論で使用するのに役立ちます。 ${\displaystyle \mathbb {N} }$

木(tree)は、集合T ⊆ ^{* で}あって、t . c ∈ Tでt ∈ ^*かつc ∈であるとき、0 ≤ c ₁ < c のすべての場合においてt ∈ Tかつt . c ₁ ∈ Tである。 Tの要素はノードと呼ばれ、空語 ε はTの(単一の)根である。すべてのt ∈ Tについて、要素t . c ∈ Tは方向cにおけるtの後続要素である。 tの後続要素の数は次数またはアリティと呼ばれ、d ( t ) と表される。ノードは、後続要素がない場合には葉である。木のすべてのノードに有限個の後続要素がある場合には有限分岐木、そうでない場合は無限分岐木と呼ばれる。パスπ は、 Tのサブセットで、 ε ∈ π であり、すべてのt ∈ Tに対して、t がリーフであるか、t . c ∈ πとなる一意のc ∈が存在するかのいずれかです。パスは有限集合または無限集合です。ツリーのすべてのパスが有限である場合、ツリーは有限と呼ばれ、そうでない場合は無限と呼ばれます。すべてのパスが無限である場合、ツリーは完全無限と呼ばれます。アルファベットΣ が与えられた場合、Σ ラベル付きツリーはペア ( T、V ) です。ここで、Tはツリーであり、V : T → Σ はTの各ノードを Σ のシンボルにマップします。ラベル付きツリーは、一般的に使用される用語ツリー構造を正式に定義します。ラベル付きツリーのセットは、ツリー言語と呼ばれます。 ${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {N} }$

ツリーの各ノードの後続ノード間に順序がある場合、ツリーは順序付きと呼ばれます。上記のツリーの定義は、後続ノード間の順序を自然に示唆しており、これを使用してツリーをランク付けできます。

ランク付けされたアルファベットの場合、追加の関数Ar : Σ →が定義されます。この関数は、アルファベットの各記号に固定のアリティを関連付けます。この場合、各t ∈ T はAr ( V ( t )) = d ( t )を満たす必要があります。このプロパティを満たすツリーはランク付けされたツリーと呼ばれます。このプロパティを（必ずしも）満たさないツリーはランクなしと呼ばれます。 ${\displaystyle \mathbb {N} }$

例えば、上記の定義は無限木オートマトンの定義で使用されます。

T = {0,1} ^*、Σ = { a、b }とします。ラベル付け関数Vを次のように定義します。ルートノードのラベル付けはV (ε) = aであり、他のすべてのノードt ∈ {0,1} ^*について、その後続ノードのラベル付けはV ( t .0) = aおよびV ( t .1) = bです。図から、 Tが（完全に）無限の二分木を形成すること は明らかです。

• コモン、ヒューバート。マックス・ドーシェ。ギルロン、レミ。ジャックマール、フィレンツェ;ルギエズ、デニス。レーディング、クリストフ。ティソン、ソフィー。マーク・トンマシ（2008年11月）。 「予選」。ツリー オートマトンのテクニックとアプリケーション(PDF) 。2014 年2 月 11 日に取得。