Tree (automata theory) とは

オートマトン理論では、ツリーは、自然数のシーケンスとしてツリー構造を表現する特別な方法です。
たとえば、ツリーの各ノードは自然数(ℕ)の集合を超える単語であり、この定義がオートマトン理論で使用されるのに役立ちます。
木は、t∈∈Tならば、t∈ℕ*とc∈thatのとき、t∈Tとt.c1∈Tがすべて0≤c1 cであるような集合T⊆ℕ*である。 Tの要素はノードとして知られており、空の単語εはTの(単一の)根です。すべてのt∈Tについて、要素t.c∈Tは方向cのtの後継です。 tの後継者の数は、その程度またはアリティと呼ばれ、d(t)として表される。後続ノードがない場合、ノードはリーフです。ツリーのすべてのノードが非常に多くの後継者を持つ場合、それは有限に、それ以外の場合は無限に分岐するツリーと呼ばれます。経路πはTの部分集合であり、ε∈πであり、すべてのt∈Tに対して、tは葉であるか、t.c∈πとなるような唯一のc∈εが存在する。パスは、有限または無限のセットです。ツリーのすべてのパスが有限である場合、ツリーは有限、そうでなければ無限と呼ばれます。すべての経路が無限であれば、木は完全無限と呼ばれます。アルファベットΣが与えられた場合、Σでラベル付けされた木はT(T、V)の対であり、Tは木であり、V:T→ΣはTの各節点をΣの記号に写像する。ラベル付きツリーは、一般的に使用される用語ツリー構造を正式に定義します。ラベル付きツリーのセットはツリー言語と呼ばれます。
各ノードの後継者の間に順序がある場合、ツリーは順序付けられたと呼ばれます。ツリーの上記の定義は、自然にツリーをランク付けするために使用できる後継者の間の順序を示唆しています。
ランク付けされたアルファベットの場合、特別な関数Ar:Σ→ℕが定義される。この機能はアルファベットの各記号に固定されたアリティを関連付けます。この場合、各t∈TはAr(V(t))= d(t)を満たさなければならない。このプロパティを満たすツリーは、ランク付けされたツリーと呼ばれます。その性質を必ずしも満たさない樹木は、無所属と呼ばれます。
たとえば、上記の定義は、無限木オートマトンの定義に使用されます。