X
XMLGuy
I initially posted this question in comp.theory but did not get much
response. Please help! I think tree automata is very well studied area
in math and computer science. Tree automata is also used often in
context of XML and will appreciate your response and opinions about
using tree automata for XML.
I am looking for an algorithm that performs intersection operation on
two tree automatas. I unable to find any in textbooks or online. Please
let me know of algorithms that you may be aware of. I am not concerned
with efficiency right now and would like to see a complete algorithm
from ground up.
I did find online book TATA:
http://www.grappa.univ-lille3.fr/tata/
Chapter 1, page 27, under "Closure Properties"
Intersection operation could be performed in terms of union and
complement. However, I am not sure how there union algorithm works. It
seems to be incomplete to me.. more specifically, i see following
problems:
a. Explanation given in this section considers two tree automata's A1
and A1. In this section, both automatons are defined to have same
alphabet set F. Why is it so? Is it not possible to perform union
operation when alphabet sets are different? or is it an unwritten
assumption that F is constructed such that it includes symbols of both
A1 and A2?
b. Definition of transition function for the product automaton seems
to be incomplete. It includes only the cases where number of states in
transition rules for a given symbol 'f' in both automatons is equal. In
other words, it does not include the following cases:
i) Product when A1 has transition f(q1, ... , qn) -> q and A2 has
transition rule f(q'2, ..., q'm) -> q' where n != m.
ii) For a transition rule f(q1, ... , qn) -> q in A1, there is no
corresponding rule in A2 (A2 does not have transition for f).
Am i wrong / correct?
I would also appreciate if you can point me to good reference that give
formal description of tree automatas with variables.
response. Please help! I think tree automata is very well studied area
in math and computer science. Tree automata is also used often in
context of XML and will appreciate your response and opinions about
using tree automata for XML.
I am looking for an algorithm that performs intersection operation on
two tree automatas. I unable to find any in textbooks or online. Please
let me know of algorithms that you may be aware of. I am not concerned
with efficiency right now and would like to see a complete algorithm
from ground up.
I did find online book TATA:
http://www.grappa.univ-lille3.fr/tata/
Chapter 1, page 27, under "Closure Properties"
Intersection operation could be performed in terms of union and
complement. However, I am not sure how there union algorithm works. It
seems to be incomplete to me.. more specifically, i see following
problems:
a. Explanation given in this section considers two tree automata's A1
and A1. In this section, both automatons are defined to have same
alphabet set F. Why is it so? Is it not possible to perform union
operation when alphabet sets are different? or is it an unwritten
assumption that F is constructed such that it includes symbols of both
A1 and A2?
b. Definition of transition function for the product automaton seems
to be incomplete. It includes only the cases where number of states in
transition rules for a given symbol 'f' in both automatons is equal. In
other words, it does not include the following cases:
i) Product when A1 has transition f(q1, ... , qn) -> q and A2 has
transition rule f(q'2, ..., q'm) -> q' where n != m.
ii) For a transition rule f(q1, ... , qn) -> q in A1, there is no
corresponding rule in A2 (A2 does not have transition for f).
Am i wrong / correct?
I would also appreciate if you can point me to good reference that give
formal description of tree automatas with variables.