An extension of data automata that captures XPath

DOI10.2168/LMCS-8(1:5)2012MaRDI QIDQ2881071zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(11)

• Alternating automata on data trees and XPath satisfiability
• scientific article; zbMATH DE number 7407777 (Why is no real title available?)
• 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

Describes a project that uses

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)