Please use this identifier to cite or link to this item:

The Regularity of two-way nondeterministic tree automata languages

Authors Brüggemann-Klein, Anne
Wood, Derick
Issue Date 2000-10-05
Source International Journal of Foundations of Computer Science , v.13, 2002, P.67-81
Summary 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 extended 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.
Language English
Format Technical report
Files in this item:
File Description Size Format
200010.pdf 248647 B Adobe PDF