Tree automaton
≈ 8 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of trees. As with classical automata, finite tree automata (FTA) can be either a deterministic automaton or not. According to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down. This is an important issue, as although non-deterministic (ND) top-down and ND bottom-up tree automata are equivalent in expressive power, deterministic top-down automata are strictly less powerful than their deterministic bottom-up counterparts, because tree properties specified by deterministic top-down tree automata can only depend on path properties. (Deterministic bottom-up tree automata are as powerful as ND tree automata.)
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines. The following article deals with branching tree automata, which correspond to regular languages of trees. As with classical automata, finite tree automata (FTA) can be either a deterministic automaton or not. According to how the automaton processes the input tree, finite tree automata can be of two types: (a) bottom up, (b) top down. This is an important issue, as although non-deterministic (ND) top-down and ND bottom-up tree automata are equivalent in expressive power, deterministic top-down automata are strictly less powerful than their deterministic bottom-up counterparts, because tree properties specified by deterministic top-down tree automata can only depend on path properties. (Deterministic bottom-up tree automata are as powerful as ND tree automata.) For n=0, that is, for a constant symbol f, the above transition rule definition reads f() → q(f()); often the empty parentheses are omitted for convenience: f → q(f). Since these transition rules for constant symbols (leaves) do not require a state, no explicitly defined initial states are needed. A bottom-up tree automaton is run on a ground term over F, starting at all its leaves simultaneously and moving upwards, associating a run state from Q with each subterm. The term is accepted if its root is associated to an accepting state from . A top-down finite tree automaton over F is defined as a tuple (Q, F, Q i , Δ), with two differences with bottom-up tree automata. First, , the set of its initial states, replaces ; second, its transition rules are oriented conversely: q(f(x 1 ,...,x n )) → f(q 1 (x 1 ),...,q n (x n )), for an n-ary , and x i variables denoting subtrees. That is, members of Δ are here rewrite rules from nodes whose roots are states to nodes whose children's roots are states. A top-down automaton starts in some of its initial states at the root and moves downward along branches of the tree, associating along a run a state with each subterm inductively. A tree is accepted if every branch can be gone through this way. A tree automaton is called deterministic (abbreviated DFTA) if no two rules from Δ have the same left hand side; otherwise it is called nondeterministic (NFTA). Non-deterministic top-down tree automata have the same expressive power as non-deterministic bottom-up ones; the transition rules are simply reversed, and the final states become the initial states. In contrast, deterministic top-down tree automata are less powerful than their bottom-up counterparts, because in a deterministic tree automaton no two transition rules have the same left-hand side. For tree automata, transition rules are rewrite rules; and for top-down ones, the left-hand side will be parent nodes. Consequently, a deterministic top-down tree automaton will only be able to test for tree properties that are true in all branches, because the choice of the state to write into each child branch is determined at the parent node, without knowing the child branches contents. For example, if F consists of f, g, and a, which are 2ary, 1ary, and 0ary, respectively, the set of all terms having a ground instance of f(a,g(x)) as a subterm, can be recognized by a bottom-up DFTA, but not by a top-town DFTA.{{efn|1= Let Q = { q a , q g , q f , q 0 }, with the informal meaning q a : "saw an a", q g : "saw some g(...)", q f : saw some f(a,g(...))", q 0 : "saw none of those". Let Q f = { q f } be the set of final states. The transition rules set Δ = { a → q a (a), f(q a (x),q g (y)) → q f (f(x,y)) } ∪ { g(q f (x)) → q f (g(x)) } ∪ { f(q f (x),q(y)) → q f (f(x,y)), f(q(x),q f (y)) → q f (f(x,y)), : q ∈ Q } ∪ { g(q(x)) → q g (g(x)), : q ∈ Q \ { q f } } ∪ { f(q g (x),q(y)) → q 0 (f(x,y)), f(q(x),q a (y)) → q 0 (f(x,y)) : q ∈ Q } maintains the informal meanings of the states during bottom-up movement through a tree t and hence accepts t if, and only if, t somewhere contains a subtree f(a,g(...)).}} Infinite-tree automata extend top-down automata to infinite trees, and can be used to prove decidability of S2S, the monadic second-order theory with two successors. Finite tree automata (nondeterministic if top-down) suffice for WS2S.
Bottom-up automaton accepting boolean lists
Employing coloring to distinguish members of F and Q, and using the ranked alphabet F={ , , , (.,.) }, with having arity 2 and all other symbols having arity 0, a bottom-up tree automaton accepting the set of all finite lists of boolean values can be defined as (Q, F, Q f , Δ) with and Δ consisting of the rules In this example, the rules can be understood intuitively as assigning to each term its type in a bottom-up manner; e.g. rule (4) can be read as "A term (x 1 ,x 2 ) has type , provided x 1 and x 2 has type and , respectively". An accepting example run is Cf. the derivation of the same term from a regular tree grammar corresponding to the automaton, shown at Regular tree grammar#Examples. A rejecting example run is Intuitively, this corresponds to the term ( , ) not being well-typed.
Top-down automaton accepting multiples of 3 in binary notation
| | | | |} Using the same colorization as above, this example shows how tree automata generalize ordinary string automata. The finite deterministic string automaton shown in the picture accepts all strings of binary digits that denote a multiple of 3. Using the notions from Deterministic finite automaton#Formal definition, it is defined by: the set Q of states being { , , }, the input alphabet being { , }, the initial state being , the set of final states being { }, and the transitions being as shown in column (B) of the table. In the tree automaton setting, the input alphabet is changed such that the symbols and are both unary, and a nullary symbol, say is used for tree leaves. For example, the binary string " " in the string automaton setting corresponds to the term " ( ( ( )))" in the tree automaton setting; this way, strings can be generalized to trees, or terms. The top-down finite tree automaton accepting the set of all terms corresponding to multiples of 3 in binary string notation is then defined by: the set Q of states being still { , , }, the ranked input alphabet being { , , }, with Arity( )=Arity( )=1 and Arity( )=0, as explained, the set of initial states being { }, and the transitions being as shown in column (C) of the table. For example, the tree " ( ( ( )))" is accepted by the following tree automaton run: In contrast, the term " ( ( ))" leads to following non-accepting automaton run: Since there are no other initial states than to start an automaton run with, the term " ( ( ))" is not accepted by the tree automaton. For comparison purposes, the table gives in column (A) and (D) a (right) regular (string) grammar, and a regular tree grammar, respectively, each accepting the same language as its automaton counterpart. For the language of all finite lists of boolean values from the above example, all terms beyond the height limit k=2 can be pumped, since they need to contain an occurrence of . For example, all belong to that language.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1374643648 under CC BY-SA 4.0; modifications have been made.