|
| << previous | next >> |
Journal description
All volumes of the corresponding journal
All issues of the corresponding volume
All articles of the corresponding issues
Details for article 5 of 6 found articles
| Title: |
One-Visit Caterpillar Tree Automata |
| Author: |
Alexander Okhotin Kai Salomaa Michael Domaratzki |
| Appeared in: |
Fundamenta informaticae |
| Paging: | Volume 52 (2003) nr. 4 pages 361-375 |
| Year: |
2003-07-11 |
| Contents: |
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. |
| Publisher: |
IOS Press |
| Source file: |
Elektronische Wetenschappelijke Tijdschriften |
Details for article 5 of 6 found articles
| << previous | next >> |