TY - GEN
T1 - Regularly extended two-way nondeterministic tree automata
AU - Brüggemann-Klein, Anne
AU - Wood, Derick
N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.
PY - 2001
Y1 - 2001
N2 - We establish that regularly extended two-way nondeterministic tree automata with unranked alphabets have the same expressive power as regularly extended nondeterministic tree automata with unranked alphabets. We obtain this result by establishing regularly ex-tended versions of a congruence on trees and of a congruence on, so called, views. Our motivation for the study of these tree models is the Extensible Markup Language (XML), a metalanguage for defining document grammars. Such grammars have regular sets of right-hand sides for their productions and tree automata provide an alternative and useful modeling tool for them. In particular, we believe that they provide a useful computational model for what we call caterpillar expressions.
AB - We establish that regularly extended two-way nondeterministic tree automata with unranked alphabets have the same expressive power as regularly extended nondeterministic tree automata with unranked alphabets. We obtain this result by establishing regularly ex-tended versions of a congruence on trees and of a congruence on, so called, views. Our motivation for the study of these tree models is the Extensible Markup Language (XML), a metalanguage for defining document grammars. Such grammars have regular sets of right-hand sides for their productions and tree automata provide an alternative and useful modeling tool for them. In particular, we believe that they provide a useful computational model for what we call caterpillar expressions.
UR - https://www.scopus.com/pages/publications/84954435315
U2 - 10.1007/3-540-44674-5_4
DO - 10.1007/3-540-44674-5_4
M3 - Conference contribution
AN - SCOPUS:84954435315
SN - 3540424911
SN - 9783540424918
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 57
EP - 66
BT - Implementation and Application of Automata - 5th International Conference, CIAA 2000, Revised Papers
A2 - Yu, Sheng
A2 - Paun, Andrei
PB - Springer Verlag
T2 - 5th International Conference on Implementation and Application of Automata, CIAA 2000
Y2 - 24 July 2000 through 25 July 2000
ER -