License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.93
URN: urn:nbn:de:0030-drops-30029
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3002/
Figueira, Diego ;
Segoufin, Luc
Bottom-up automata on data trees and vertical XPath
Abstract
A data tree is a tree whose every node carries a label from a finite alphabet and a datum from some infinite domain. We introduce a new model of automata over unranked data trees with a decidable emptiness problem. It is essentially a bottom-up alternating automaton with one register, enriched with epsilon-transitions that perform tests on the data values of the subtree. We show that it captures the expressive power of the vertical fragment of XPath -- containing the child, descendant, parent and ancestor axes -- obtaining thus a decision procedure for its satisfiability problem.
BibTeX - Entry
@InProceedings{figueira_et_al:LIPIcs:2011:3002,
author = {Diego Figueira and Luc Segoufin},
title = {{Bottom-up automata on data trees and vertical XPath}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {93--104},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-25-5},
ISSN = {1868-8969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3002},
URN = {urn:nbn:de:0030-drops-30029},
doi = {10.4230/LIPIcs.STACS.2011.93},
annote = {Keywords: Decidability, XPath, Data trees, Bottom-up tree automata}
}
Keywords: |
|
Decidability, XPath, Data trees, Bottom-up tree automata |
Collection: |
|
28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) |
Issue Date: |
|
2011 |
Date of publication: |
|
11.03.2011 |