Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/592
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.author | NEVEN, Frank | - |
dc.contributor.author | Schwentick, Thomas | - |
dc.date.accessioned | 2005-02-11T14:56:58Z | - |
dc.date.available | 2005-02-11T14:56:58Z | - |
dc.date.issued | 2003 | - |
dc.identifier.citation | Information and Computation, 183(1). p. 86-103 | - |
dc.identifier.issn | 0890-5401 | - |
dc.identifier.uri | http://hdl.handle.net/1942/592 | - |
dc.description.abstract | Tree-walking automata (TWAs) recently received new attention in the fields of formal languages and databases. To achieve 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 semistructured data. | - |
dc.language.iso | en | - |
dc.publisher | Elsevier | - |
dc.title | On the power of tree-walking automata. | - |
dc.type | Journal Contribution | - |
dc.identifier.epage | 103 | - |
dc.identifier.issue | 1 | - |
dc.identifier.spage | 86 | - |
dc.identifier.volume | 183 | - |
local.bibliographicCitation.jcat | A1 | - |
local.type.refereed | Refereed | - |
local.type.specified | Article | - |
dc.bibliographicCitation.oldjcat | A1 | - |
dc.identifier.doi | 10.1016/S0890-5401(03)00013-0 | - |
dc.identifier.isi | 000183004100006 | - |
item.fullcitation | NEVEN, Frank & Schwentick, Thomas (2003) On the power of tree-walking automata.. In: Information and Computation, 183(1). p. 86-103. | - |
item.fulltext | No Fulltext | - |
item.validation | ecoom 2004 | - |
item.contributor | NEVEN, Frank | - |
item.contributor | Schwentick, Thomas | - |
item.accessRights | Closed Access | - |
crisitem.journal.issn | 0890-5401 | - |
crisitem.journal.eissn | 1090-2651 | - |
Appears in Collections: | Research publications |
SCOPUSTM
Citations
12
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
9
checked on Sep 20, 2024
Page view(s)
64
checked on Jul 28, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.