Alternating automata on data trees and XPath satisfiability

DOI10.1145/1929954.1929956zbMath1351.68141arXiv0805.0330OpenAlexW2056864188MaRDI QIDQ2946637

Ranko Lazić, Marcin Jurdziński

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

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

Related Items (6)

Reasoning about integrity constraints for tree-structured data ⋮ Unnamed Item ⋮ A note on the emptiness problem for alternating finite-memory automata ⋮ Logics of Repeating Values on Data Trees and Branching Counter Systems ⋮ Linearizing well quasi-orders and bounding the length of bad sequences ⋮ Complexity Hierarchies beyond Elementary

Uses Software

• XPath

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