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

lmcs:4047 - 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 : oai:arXiv.org:1710.08748
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


Share

Browsing statistics

This page has been seen 28 times.
This article's PDF has been downloaded 8 times.