Tree (automata theory)

In automata theory, a tree is a particular way of representing a mathematical tree as sequences of natural numbers.

Graphic illustration of the labeled tree described in the example

For example, each node of the tree is a word over set of natural numbers (ℕ), which helps this definition to be used in automata theory.

A tree is a set T ⊆ ℕ^* such that if t.c ∈ T, with t ∈ ℕ^* and c ∈ ℕ, then t ∈ T and t.c₁ ∈ T for all 0 ≤ c₁ < c. The elements of T are known as nodes, and the empty word ε is the (single) root of T. For every t ∈ T, the element t.c ∈ T is a successor of t in direction c. The number of successors of t is called its degree or arity, and represented as d(t). A node is a leaf if it has no successors. If every node of a tree has finitely many successors, then it is called a finitely, otherwise an infinitely branching tree. A path π is a subset of T such that ε ∈ π and for every t ∈ T, either t is a leaf or there exists a unique c ∈ ℕ such that t.c ∈ π. A path may be a finite or infinite set. If all paths of a tree are finite then the tree is called finite, otherwise infinite. A tree is called fully infinite if all its paths are infinite. Given an alphabet Σ, a Σ-labeled tree is a pair (T,V), where T is a tree and V: T → Σ maps each node of T to a symbol in Σ. A labeled tree formally defines a commonly used term tree structure. A set of labeled trees is called a tree language.

A tree is called ranked if there is an order among the successors of each of its nodes. Above definition of tree naturally suggests an order among the successors, which can be used to make the tree ranked. Sometimes, an extra function Ar: Σ → ℕ is defined. This function associates a fixed arity to each symbol of the alphabet. In this case, each t ∈ T has to satisfy Ar(V(t)) = d(t).

For example, above definition is used in the definition of an infinite tree automaton.

Example

Let T = {0,1}^* and Σ = {a,b}. We define a labeling function V as follows: the labeling for the root node is V(ε) = a and, for every other node t ∈ {0,1}^*, the labellings for its successor nodes are V(t.0) = a and V(t.1) = b. It is clear from the picture that T forms a (fully) infinite binary tree.