The Library
Alternating automata on data trees and XPath satisfiability
Tools
Jurdzinski, Marcin and Lazic, Ranko (2011) Alternating automata on data trees and XPath satisfiability. ACM Transactions on Computational Logic (TOCL), Volume 12 (Number 3). pp. 1-21. doi:10.1145/1929954.1929956 ISSN 1529-3785.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1145/1929954.1929956
Abstract
A data tree is an unranked ordered tree whose every node is labeled by a letter from a finite alphabet and an element ("datum") from an infinite set, where the latter can only be compared for equality. The article considers alternating automata on data trees that can move downward and rightward, and have one register for storing data. The main results are that nonemptiness over finite data trees is decidable but not primitive recursive, and that nonemptiness of safety automata is decidable but not elementary. The proofs use nondeterministic tree automata with faulty counters. Allowing upward moves, leftward moves, or two registers, each causes undecidability. As corollaries, decidability is obtained for two data-sensitive fragments of the XPath query language.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Algorithms, Machine theory, Trees (Graph theory), Data mining, Query languages (Computer science) | ||||
Journal or Publication Title: | ACM Transactions on Computational Logic (TOCL) | ||||
Publisher: | Association for Computing Machinery, Inc. | ||||
ISSN: | 1529-3785 | ||||
Official Date: | 2011 | ||||
Dates: |
|
||||
Volume: | Volume 12 | ||||
Number: | Number 3 | ||||
Page Range: | pp. 1-21 | ||||
DOI: | 10.1145/1929954.1929956 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Funder: | Intel Corporation |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |