Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/617
Title: On the Power of Tree-Walking Automata
Authors: NEVEN, Frank 
Schwentick, Thomas
Issue Date: 2000
Publisher: Springer-Verlag GmbH
Source: AUTOMATA LANGUAGES AND PROGRAMMING. p. 547-560
Series/Report: LECTURE NOTES IN COMPUTER SCIENCE
Series/Report no.: 1853
Abstract: Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. Towards a better understanding of their expressiveness, we characterize them in terms of transitive closure logic formulas in normal form. It is conjectured by Engelfriet and Hoogeboom that TWAs cannot define all regular tree languages, or equivalently, all of monadic second-order logic. We prove this conjecture for a restricted, but powerful, class of TWAs. In particular, we show that 1-bounded TWAs, that is TWAs that are only allowed to traverse every edge of the input tree at most once in every direction, cannot define all regular languages. We then extend this result to a class of TWAs that can simulate first-order logic (FO) and is capable of expressing properties not definable in FO extended with regular path expressions; the latter logic being a valid abstraction of current query languages for XML and semi-structured data.[-4pt]
Document URI: http://hdl.handle.net/1942/617
ISBN: 0302-9743
ISI #: 000089738700046
Category: A1
Type: Journal Contribution
Validations: ecoom 2001
Appears in Collections:Research publications

Files in This Item:
File Description SizeFormat 
12 twa.pdf246.73 kBAdobe PDFView/Open
Show full item record

WEB OF SCIENCETM
Citations

7
checked on May 22, 2022

Page view(s)

48
checked on May 25, 2022

Download(s)

172
checked on May 25, 2022

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.