2026-09-28T09:41:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3002 2026-09-22T17:09:01Z ddc:004 open_access

Bottom-up automata on data trees and vertical XPath Figueira, Diego Segoufin, Luc Decidability XPath Data trees Bottom-up tree automata 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Diego Figueira and Luc Segoufin 2011 Is Part Of LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2011.93 urn:nbn:de:0030-drops-30029 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.93 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode