Standard

One-visit caterpillar tree automata. / Okhotin, Alexander; Salomaa, Kai; Domaratzki, Michael.

в: Fundamenta Informaticae, Том 52, № 4, 01.10.2002, стр. 361-375.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Okhotin, A, Salomaa, K & Domaratzki, M 2002, 'One-visit caterpillar tree automata', Fundamenta Informaticae, Том. 52, № 4, стр. 361-375.

APA

Okhotin, A., Salomaa, K., & Domaratzki, M. (2002). One-visit caterpillar tree automata. Fundamenta Informaticae, 52(4), 361-375.

Vancouver

Okhotin A, Salomaa K, Domaratzki M. One-visit caterpillar tree automata. Fundamenta Informaticae. 2002 Окт. 1;52(4):361-375.

Author

Okhotin, Alexander ; Salomaa, Kai ; Domaratzki, Michael. / One-visit caterpillar tree automata. в: Fundamenta Informaticae. 2002 ; Том 52, № 4. стр. 361-375.

BibTeX

@article{12dd923c58e84f708c20c7644e2f5f82,
title = "One-visit caterpillar tree automata",
abstract = "We study caterpillar tree automata 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{\"u}ggemann-Klein and Wood. We establish that the k-visit property is decidable.",
keywords = "K-visit property, Markup languages, Regular tree languages, Tree automata",
author = "Alexander Okhotin and Kai Salomaa and Michael Domaratzki",
year = "2002",
month = oct,
day = "1",
language = "English",
volume = "52",
pages = "361--375",
journal = "Fundamenta Informaticae",
issn = "0169-2968",
publisher = "IOS Press",
number = "4",

}

RIS

TY - JOUR

T1 - One-visit caterpillar tree automata

AU - Okhotin, Alexander

AU - Salomaa, Kai

AU - Domaratzki, Michael

PY - 2002/10/1

Y1 - 2002/10/1

N2 - We study caterpillar tree automata 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. We establish that the k-visit property is decidable.

AB - We study caterpillar tree automata 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. We establish that the k-visit property is decidable.

KW - K-visit property

KW - Markup languages

KW - Regular tree languages

KW - Tree automata

UR - http://www.scopus.com/inward/record.url?scp=0036817529&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0036817529

VL - 52

SP - 361

EP - 375

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

SN - 0169-2968

IS - 4

ER -

ID: 41145177