Tree Automata questions

Discussion in 'XML' started by XMLGuy, Jan 13, 2005.

  1. XMLGuy

    XMLGuy Guest

    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.
    XMLGuy, Jan 13, 2005
    #1
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Pleg
    Replies:
    0
    Views:
    512
  2. defcon8
    Replies:
    5
    Views:
    3,640
    defcon8
    Jun 24, 2006
  3. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,078
  4. Replies:
    7
    Views:
    353
    defcon8
    May 14, 2006
  5. defcon8
    Replies:
    5
    Views:
    296
    defcon8
    Jun 24, 2006
Loading...

Share This Page