Game Development Reference
In-Depth Information
q in ( q in ,b,q 1 ,q 2 ) Δ
b
q 2 ( q 2 ,b,q 5 ,q 6 ) Δ
q 1
( q 1 ,a,q 3 ,q 4 ) Δ
b
q 3
q 4
q 5
q 6
b
b
b
b
a a
a a
b a
a a
.
Figure 2.10 A run of a PTA has to respect the transition relation
} . This is
the transitions, ( ρ ( u ) ,t ( u ) ( u 0) ( u 1))
Δ for all u
∈{
0 , 1
illustrated in Figure 2.10.
The acceptance condition of a PTA is defined via the priority mapping.
From games and ω -automata we already know that a sequence of states is
accepting if the maximal priority that appears infinitely often is even. We
extend this to trees by defining a run to be accepting if the state sequence
on each infinite path through the run is accepting, i.e., if on each infinite
path the maximal priority that occurs infinitely often is even.
As usual, a tree is accepted if there is an accepting run on this tree. The
language of trees accepted by
). We call a language of
infinite trees regular if it can be accepted by a parity tree automaton.
Before we come to the properties of PTAs, we make some remarks on other
acceptance conditions and give some examples:
A
is denoted by T (
A
As for games or ω -automata we can define, e.g., tree automata with Muller
or Buchi acceptance conditions.
The expressive power of Muller tree automata and parity tree automata is
the same. To transform Muller automata into parity automata one can
use the LAR construction presented in the previous section.
One can show that Buchi tree automata are weaker than parity tree
automata. The language of all trees over
such that on each path
there are finitely many b cannot be accepted by a Buchi tree automaton
but by a PTA. The PTA can easily be obtained by running the parity
word automaton from Figure 2.5 on every branch of the tree using the
transitions ( q 0 ,a,q 0 ,q 0 ), ( q 0 ,b,q 1 ,q 1 ), ( q 1 ,a,q 0 ,q 0 ), and ( q 1 ,b,q 1 ,q 1 ). A
proof that a Buchi tree automaton cannot accept this language can be
found in Thomas [1997] and in Chapter 8 of Gradel et al. [2002].
{
a, b
}
It is rather easy to see that deterministic tree automata are too weak. For
example, the set of all trees t over
{
a, b
}
such that t contains at least one