11 - Bottom-Up and Top-Down Tree Automata

Question 1

BUTA TDTA rough overview

Answer 1

BUTA = DBUTA = TDTA > DTDTA

Ranked alphabet (Σ ,rk) filite symbol set Σ and rank function rk : Σ -> N

recursive definition of yield function

BUTA is a tuple ((Σ ,rk), Q, –> Qf)
–>a Q^n x Q, where n = rk(a)

A run of a BUTA labels nodes of a tree by states
initial state: a ∈ Σ with rk(a) = 0 (leaf letters)

a tree language is regular if it has a BUTA

BUTA = DBUTA (powerset construction)
closed under complementation and union

BUTA = TDTA
just invert transition relations (but relies on nondeterminism of TDTA)

TDTA > DTDTA
By contradiction

emptiness and universality computed in O(n)
universality reduced from emptiness complement

Question 2

hot to check membership for hedge automata?

Answer 2

A DTD is a hedge automata.
hedge automata is over unranked alphabet, therefore the the transition can now be a reg lag
processesd bottom-up

to check membership of horizontal language of an NFA, we construct a mapping using a powerset of Q

give NHA A (Q,–>,Qf)
tree t:T –> Σ
construct mapping ϱ : T –> P(Q)

It will check the tree using the powerset of possible states that are reachable. If an qf is in the set of states of root, then accept.