Figueira, Diego and Segoufin, Luc - Bottom-up automata on data trees and vertical XPath

lmcs:4044 - Logical Methods in Computer Science, November 6, 2017, Volume 13, Issue 4
Bottom-up automata on data trees and vertical XPath

Authors: Figueira, Diego and Segoufin, Luc

A data tree is a finite 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 that can store one data value and can be used to perform equality tests with the data values occurring within the subtree of the current node. 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.

Source :
DOI : 10.23638/LMCS-13(4:5)2017
Volume: Volume 13, Issue 4
Published on: November 6, 2017
Submitted on: November 2, 2017
Keywords: Computer Science - Databases


Consultation statistics

This page has been seen 174 times.
This article's PDF has been downloaded 103 times.