Extending two-variable logic on data trees with order on data values and its automata
From MaRDI portal
Publication:5410335
DOI10.1145/2559945zbMath1287.03077arXiv1212.3251OpenAlexW1992955510MaRDI QIDQ5410335
Publication date: 16 April 2014
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1212.3251
Analysis of algorithms and problem complexity (68Q25) Logic in computer science (03B70) Automata and formal grammars in connection with logical questions (03D05) Data structures (68P05)
Related Items
Complexity of Two-Variable Logic on Finite Trees, On temporal logics with data variable quantifications: decidability and complexity, Weighted Unranked Tree Automata over Tree Valuation Monoids and Their Characterization by Weighted Logics, An automata-theoretic approach to the verification of distributed algorithms, Unnamed Item, $$\mathbb {N}$$ -Memory Automata over the Alphabet $$\mathbb {N}$$
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Elements of finite model theory.
- Finite-memory automata
- XML with data values: Typechecking revisited.
- Characterizing derivation trees of context-free grammars through a generalization of finite automata theory
- Alternating register automata on finite words and trees
- Feasible Automata for Two-Variable Logic with Successor on Data Words
- LTL with the freeze quantifier and register automata
- Safety alternating automata on data words
- Two-variable logic on data words
- Relating timed and register automata
- Two-variable logic on data trees and XML reasoning
- On XML integrity constraints in the presence of DTDs
- Variable Automata over Infinite Alphabets
- Automata vs. Logics on Data Words
- Two Variables and Two Successors
- Optimizing Conjunctive Queries over Trees Using Schema Information
- On the Complexity of Verifying Consistency of XML Specifications
- Presburger arithmetic with unary predicates is Π11 complete
- On the Satisfiability of Two-Variable Logic over Data Words
- Finite state machines for strings over infinite alphabets
- Automated Deduction – CADE-20
- Bounded Depth Data Trees
- A Decidable Temporal Logic of Repeating Values
- Automata, Languages and Programming
- Two-Variable Logic with Two Order Relations
