Database Reference
In-Depth Information
} that, together with each
on binary trees. A binary tree domain D is a subset of
{
0 , 1
w
D , contains all its prefixes (including
ε
), and such that for each w
D , either both w
·
0
and w
1arein D , or none of them is. These define the nodes of a tree, as is shown in the
picture below:
·
ε
0
1
00
01
10
11
A tree over
is
a labeling function. A nondeterministic (bottom-up) tree automaton (NTA) is defined as a
tuple
Σ
is then a pair T =( D ,
λ
),where D is a binary tree domain and
λ
: D
Σ
A
=( Q ,
Σ
, q 0 , F ,
δ
), where the only difference with the definition of an NFA is that
2 Q . The intuition behind this transition function
is that if states q and q are already assigned to left and right children of a node v labeled
a , then any state from
the transition function is
δ
: Q
×
Q
× Σ
( q , q , a ) can be assigned to v .
δ
Formally, a run of
A
on a tree T =( D ,
λ
) is a function
ρ
: D
Q such that:
( q 0 , q 0 , a ),and
if v has children v 0 , v 1 and λ ( v )= a ,thenρ( v ) δ (ρ( v 0 ) , ρ( v 1 ) , a ).
if v is a leaf and
λ
( v )= a ,then
ρ
( v )
δ
A run is accepting if
ρ
(
ε
)
F . With this, the notions of trees accepted by
A
and the
language
) are defined as before.
The same questions we considered for word automata can be asked about tree automata.
Nonemptiness, i.e., checking whether
L
(
A
= 0, is solvable in polynomial time, and is
in fact P TIME -complete. The universality problem, i.e., checking whether every tree is
accepted by
L
(
A
)
A
,isE XPTIME -complete. The containment problem for two tree automata is
E XPTIME -complete as well.
Search WWH ::




Custom Search