Information Technology Reference
In-Depth Information
f/g
:
γ
0
g
g
f
:
γ
0
f/g
:
γ
0
(0
,
)
(1
,γ
0
)
(1
,γ
1
γ
0
)
g
:
γ
1
g
:
γ
1
g
f
:
γ
0
g
:
γ
1
g
:
γ
0
g
f
(1
,γ
0
)
(1
,γ
1
γ
0
)
,γ
0
γ
1
γ
0
)
f
:
γ
0
f
0
1
2
g
g
(2
,γ
1
γ
0
)
(2
,γ
0
)
(2
,
)
g
:
γ
0
(a) VPA
A
over alphabet
Σ
=
{f,g}
.
(b) Run of
A
on [
t
].
Fig. 2.
An automaton and one of its runs
A
on a linearization [
t
]=
a
1
···
a
n
of
t
∈
T
Σ
is a sequence
A
run
of a VPA
(
q
0
,σ
0
)
···
(
q
n
,σ
n
) of configurations such that (
q
0
,σ
0
) is initial, and for every
a
i
−→
1
≤
i
≤
n
,(
q
i−
1
,σ
i−
1
)
(
q
i
,σ
i
).Sucharunis
accepting
if (
q
n
,σ
n
) is final.
Atree
t
is
accepted
by
if there is an accepting run on its linearization [
t
].
The set of accepted trees is called the
language
of
A
).
1
For
instance, given a tree
t
, the VPA of Figure 2a checks whether
t
has a
g
-node
with an
f
-child. An accepting run on [
t
]forthetree
t
of Figure 1, is depicted in
Figure 2b.
A
and is written
L
(
A
2.3 Universality and Right-Universality
We conclude the section of preliminaries with the notions of universality
2
and
right-universality, that we will study in the remainder of the paper.
Definition 2.
AVPA
A
over
Σ
is said
universal
if
A
accepts all trees
t ∈ T
Σ
,
i.e.
L
(
A
)=
T
Σ
.Let
u ∈
Pref
(
T
Σ
)
\{}
be a non empty prefix of
[
t
0
]
for some
tree
t
0
∈
T
Σ
.TheVPA
A
is said
right-universal w.r.t.
u
if for all trees
t
∈
T
Σ
,
if
u
is a prefix of
[
t
]
,then
t
is accepted by
A
.
In other words, right-universality w.r.t.
u
allows to assert that any tree lin-
earization beginning with
u
is accepted by the automaton. In this definition,
notice that when
u
=[
t
0
], then
A
is right-universal w.r.t.
u
iff
t
0
is accepted by
A
. Moreover, as a universal VPA is right-universal w.r.t. all non empty words
u
Pref
(
T
Σ
), we assume in the sequel that VPAs are not universal.
In this article, our objective is to propose an
incremental
algorithm for right-
universality of a VPA
∈
, in the sense described in the introduction (see Algo-
rithm 1). More precisely, the linearization [
t
0
]ofagiventree
t
0
is read letter
by letter
3
, and while
A
is not right-universal w.r.t. the current read prefix
u
of
[
t
0
], the next letter of [
t
0
] is read. When processing a new letter, we try to reuse
A
1
VPAs considered in this article are tree acceptors, with acceptance on empty stack.
2
This notion of universality is different from the one proposed for usual VPAs, where
a VPA is universal if it accepts all words of (
Σ ∪ Σ
)
∗
(and not only linearizations of
trees).
3
[
t
0
]isthetrace
w
of Algorithm 1.
