One-Visit Caterpillar Tree Automata

Article type: Research Article

Authors: Okhotin, Alexander | Salomaa, Kai | Domaratzki, Michael

Affiliations: School of Computing, Queen's University, Kingston, Ontario, Canada K7L 3N6

Abstract: 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.

Keywords: tree automata, regular tree languages, markup languages, k-visit property

Journal: Fundamenta Informaticae, vol. 52, no. 4, pp. 361-375, 2002