Alternating automata on data trees and XPath satisfiability

DOI10.1145/1929954.1929956MaRDI QIDQ2946637zbMATH OpenOpenAlexFDO

Authors Marcin Jurdziński, Ranko Lazić

Publication date 17 September 2015

Published in ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.0330

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Database theory (68P15) Formal languages and automata (68Q45)

Abstract: A data tree is an unranked ordered tree whose every node is labelled by a letter from a finite alphabet and an element ("datum") from an infinite set, where the latter can only be compared for equality. The article considers alternating automata on data trees that can move downward and rightward, and have one register for storing data. The main results are that nonemptiness over finite data trees is decidable but not primitive recursive, and that nonemptiness of safety automata is decidable but not elementary. The proofs use nondeterministic tree automata with faulty counters. Allowing upward moves, leftward moves, or two registers, each causes undecidability. As corollaries, decidability is obtained for two data-sensitive fragments of the XPath query language.

Recommendations

• scientific article; zbMATH DE number 5999538
• Bottom-up automata on data trees and vertical \(\mathsf{XPath}\)
• Alternating register automata on finite words and trees
• Decidability of downward XPath
• An extension of data automata that captures XPath

Cited in

(24)

• Efficient inclusion checking for deterministic tree automata and XML schemas
• Reasoning about integrity constraints for tree-structured data
• Model theory of XPath on data trees. II: Binary bisimulation and definability
• A note on the emptiness problem for alternating finite-memory automata
• Complexity hierarchies beyond elementary
• An extension of data automata that captures XPath
• Alternating register automata on finite words and trees
• Model theory of XPath on data trees. I: Bisimulation and characterization
• Safety alternating automata on data words
• Decidability of downward XPath
• Decidable classes of documents for XPath
• Logics of repeating values on data trees and branching counter systems
• scientific article; zbMATH DE number 5999538 (Why is no real title available?)
• Future-Looking Logics on Data Words and Trees
• Two-variable logic on data trees and XML reasoning
• Bottom-up automata on data trees and vertical \(\mathsf{XPath}\)
• scientific article; zbMATH DE number 7136664 (Why is no real title available?)
• Bounded Depth Data Trees
• Branching in well-structured transition systems (invited talk)
• Nominal tree automata with name allocation
• Constraint automata on infinite data trees: from \(\mathrm{CTL}(\mathbb{Z})/\mathrm{CTL}^*(\mathbb{Z})\) to decision procedures
• Constraint automata on infinite data trees: from CTL\((\mathbb{Z})\text{CTL}^*(\mathbb{Z})\) to decision procedures
• Linearizing well quasi-orders and bounding the length of bad sequences
• The complexity of tree automata and XPath on grammar-compressed trees

Describes a project that uses

Uses Software

• XPath

This page was built for publication: Alternating automata on data trees and XPath satisfiability

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2946637)