Bottom-up automata on data trees and vertical XPath

Figueira, Diego; Segoufin, Luc

doi:10.4230/LIPIcs.STACS.2011.93

Document

Bottom-up automata on data trees and vertical XPath

Authors Diego Figueira, Luc Segoufin

Part of: Volume: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Part of: Series: Leibniz International Proceedings in Informatics (LIPIcs)
Part of: Conference: Symposium on Theoretical Aspects of Computer Science (STACS)
License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
Publication Date: 2011-03-11

PDF

File

PDF

LIPIcs.STACS.2011.93.pdf

Filesize: 2 MB
12 pages

Document Identifiers

DOI: 10.4230/LIPIcs.STACS.2011.93
URN: urn:nbn:de:0030-drops-30029

Subject Classification

Keywords

Decidability
XPath
Data trees
Bottom-up tree automata

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.

Cite As Get BibTex

Diego Figueira and Luc Segoufin. Bottom-up automata on data trees and vertical XPath. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 93-104, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011) https://doi.org/10.4230/LIPIcs.STACS.2011.93

Author Details

Diego Figueira

Luc Segoufin

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail

	
		OSZAR »