On ground tree transformations and congruences induced by tree automata

✍ Scribed by Sándor Vágvölgyi

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 230 KB
• Volume: 304
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(03)00279-2

✦ Synopsis

For a tree automaton A over a ranked alphabet , we study the ground tree transformation (A) induced by A and the restriction Â(A) of the congruence ↔ * A to terms over . We deÿne a congruence relation ⊆ A × A on A, called the determiner of A, and the quotient tree automaton A= . We show the following results. It is decidable if Â(A) = (A). If A is deterministic, then Â(A) = (A). The determiner of A can be e ectively constructed, A= is deterministic, and Â(A) = Â(A= ). For a connected tree automaton A, (A) = (A= ) if and only if (A) = (B) for some deterministic tree automaton B if and only if Â(A) = (A).