One-Visit Caterpillar Tree Automata

• Autorzy: Okhotin A. , Salomaa K. , Domaratzki M.
• Języki publikacji: EN

Abstrakty

EN

We study caterpillar tree automata [3] that are restricted to enter any subtree at most one time (or k times). We show that, somewhat surprisingly, the deterministic one-visit automata can already, for instance, evaluate trees where the nodes represent some non-associative operations. We show that there exist regular tree languages that cannot be accepted by a one-visit automaton, thus proving a weakened form of a conjecture of Brüggemann-Klein and Wood [3]. We establish that the k-visit property is decidable.

Słowa kluczowe

EN

tree automata; regular tree languages; markup languages; k-visit property

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 52, nr 4
• Strony: 361--375
• Opis fizyczny: bibliogr. 11 poz.

Twórcy

autor

Okhotin A.

autor

Salomaa K.

autor

Domaratzki M.

• School of Computing, Queen's University, Kingston, Ontario, Canada K7L3N6,