Database Reference
In-Depth Information
Given an unranked tree
T
,a
run
of
A
on
T
is a function
ρ
A
:
T
→
Q
that assigns states to
nodes. This function must satisfy the following condition:
•
if
s
is a node with label
a
and children
s
1
,...,
s
n
ordered by the sibling relation as
s
1
→
···→
s
n
, then the word
ρ
A
(
s
1
)
...
ρ
A
(
s
n
) over
Q
must be in the language
δ
(
ρ
A
(
s
)
,
a
).
Note that if
s
is a leaf, this condition states that a run can assign a state
q
to
s
only if the
empty string
(
q
,
a
).
Arunis
accepting
if it assigns an accepting state to the root, i.e.,
ε
is in
δ
ρ
A
(
ε
)
∈
F
.Atree
T
is
accepted by
A
if there is an accepting run. The
language recognized by
A
, denoted by
L
(
A
), is the set of trees accepted by
A
.
maps pairs state-
letter to NFAs over
Q
. We will call these NFAs
horizontal automata
. Assuming this repre-
sentation, the size of
A
, written as
A
, is the number of states plus the total size of the
horizontal automata (number of states plus the size of transition relation). It is known that
testing nonemptiness and testing membership can be done in polynomial time, in the size
of the automaton. An automaton is (bottom-up) deterministic if for each label
The standard representation of UNFTAs uses NFAs for transitions:
δ
∈
Γ
,the
languages
(
q
,
) are pairwise disjoint for
q
ranging over all states of the automaton. Note
that in this case each tree admits at most one run. For such automata we assume that all
transitions are represented by DFAs, and refer to them as UFTA(DFA).
A
(regular) schema
δ
S
over the set of element types
Γ
and the set of attributes
Att
2
Att
consists of an UNFTA
A
over
Γ
and a mapping
A
S
:
Γ
→
that assigns a (possibly
empty) set of attributes to each element type. The size
S
is
A
plus
|
Att
|
.Atree
T
conforms to such a schema if it is accepted by
and the set of attributes of each
-labeled
node is
A
S
(
). Testing conformance to a schema can be done in polynomial time, even if
the schema is counted as a part of the input.
DTDs can be seen as a restricted form of regular schemas. A DTD
D
=(
P
D
,
A
D
,
r
) over
A
Γ
and
Att
can be presented as
S
D
=(
A
D
,
A
D
),where
A
D
=(
Q
,
F
,
δ
) is an UNFTA defined
as follows:
•
the set of states
Q
is
{
q
a
|
a
∈
Γ
}
;
•
the set of final states
F
is
{
q
r
}
;
•
the transition function is defined as follows:
(
q
,
) is the language of the regular ex-
pression
P
D
(
), with each letter
a
replaced by
q
a
,and
δ
(
q
,
)=/0for
=
.
δ
Then the set of trees that conform to
D
is exactly the set of trees that conform to
S
D
.
Coming back to our example, the labeling alphabet consists of
europe
,
country
,and
ruler
. The automaton will have three states:
q
europe
,
q
country
,and
q
ruler
;thestate
q
europe
is the only final state. The transitions are as follows:
(
q
europe
,
europe
) =
q
country
δ
(
q
country
,
country
)=
q
ruler
δ
δ
(
q
ruler
,
ruler
) =
ε
.
For all other combinations (
q
,
a
),wehave
δ
(
q
,
a
)=0.
