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.