Two-variable logic on data trees and XML reasoning
From MaRDI portal
Publication:3452211
DOI10.1145/1516512.1516515zbMath1325.68078OpenAlexW2053455078MaRDI QIDQ3452211
Thomas Schwentick, Luc Segoufin, Anca Muscholl, Mikołaj Bojańczyk
Publication date: 11 November 2015
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1516512.1516515
Related Items
Expressive Completeness of Separation Logic with Two Variables and No Separating Conjunction ⋮ Two-Variable Logic with Counting and Trees ⋮ Deciding twig-definability of node selecting tree automata ⋮ Complexity of Two-Variable Logic on Finite Trees ⋮ Future-Looking Logics on Data Words and Trees ⋮ Characterizations for \(\mathrm{XPath}_{\mathcal{R}}(\downarrow)\) ⋮ Reasoning about integrity constraints for tree-structured data ⋮ XML Schema Mappings ⋮ Model theory of XPath on data trees. II: Binary bisimulation and definability ⋮ Axiomatizations for downward XPath on data trees ⋮ Nonelementary Complexities for Branching VASS, MELL, and Extensions ⋮ Complexity results on register context-free grammars and related formalisms ⋮ Set augmented finite automata over infinite alphabets ⋮ The reachability problem for branching vector addition systems requires doubly-exponential space ⋮ Structural characterizations of the navigational expressiveness of relation algebras on a tree ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Conjunctive query containment over trees using schema information ⋮ An automata-theoretic approach to the verification of distributed algorithms ⋮ Reasoning about functional and full hierarchical dependencies over partial relations ⋮ Unnamed Item ⋮ Logics of Repeating Values on Data Trees and Branching Counter Systems ⋮ On Synthesis of Specifications with Arithmetic ⋮ Walking on data words ⋮ On regular paths with counting and data tests ⋮ Variable Tree Automata over Infinite Ranked Alphabets ⋮ Extending two-variable logic on data trees with order on data values and its automata ⋮ Model checking memoryful linear-time logics over one-counter automata ⋮ Reasoning about XML with temporal logics and automata ⋮ Complexity of Data Tree Patterns over XML Documents ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Regular Programming for Quantitative Properties of Data Streams ⋮ Forward analysis for WSTS, part I: completions ⋮ Logical Foundations of XML and XQuery ⋮ Hilbert-Style Axiomatization for Hybrid XPath with Data ⋮ Unnamed Item ⋮ Testing XML constraint satisfiability ⋮ Emptiness and finiteness for tree automata with global reflexive disequality constraints