Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: markup languages

Sortuj według:

Ogranicz wyniki do:

One-Visit Caterpillar Tree Automata

Okhotin A., Salomaa K., Domaratzki M.

Fundamenta Informaticae

2002

Vol. 52, nr 4

361-375

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.