An extension of data automata that captures XPath

DOI10.2168/LMCS-8(1:5)2012zbMATH Open1241.68077arXiv1201.0597OpenAlexW2054193719MaRDI QIDQ2881071FDOQ2881071

Authors: Mikołaj Bojańczyk, Sławomir Lasota 

Publication date: 3 April 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: We define a new kind of automata recognizing properties of data words or data trees and prove that the automata capture all queries definable in Regular XPath. We show that the automata-theoretic approach may be applied to answer decidability and expressibility questions for XPath.

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

Recommendations

• scientific article; zbMATH DE number 5999538
• Alternating automata on data trees and XPath satisfiability
• Bottom-up automata on data trees and vertical \(\mathsf{XPath}\)
• Decidability of downward XPath
• On regular paths with counting and data tests

zbMATH Keywords

data automataautomata on data words and treesregular XPathsatisfiability of XPath queries

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Searching and sorting (68P10)

Cited In (11)

• The factorisation forest theorem
• On regular paths with counting and data tests
• Nondeterministic and co-nondeterministic implies deterministic, for data languages
• An automaton over data words that captures EMSO logic
• Hilbert-style axiomatization for hybrid XPath with data
• A Note on C² Interpreted over Finite Data-Words
• On temporal logics with data variable quantifications: decidability and complexity
• First order Büchi automata and their application to verification of LTL specifications
• On notions of regularity for data languages
• Alternating automata on data trees and XPath satisfiability
• Title not available (Why is that?)

Uses Software

• XPath

This page was built for publication: An extension of data automata that captures XPath

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