On the satisfiability of two-variable logic over data words

DOI10.1007/978-3-642-16242-8_18MaRDI QIDQ4933309zbMATH OpenOpenAlexFDO

Authors Claire David, Tony Tan, Leonid Libkin

Publication date 12 October 2010

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16242-8_18

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70) Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Two-variable logic on data trees and XML reasoning
• Two-variable logic on data words
• Two-variable logic on 2-dimensional structures
• Complexity of two-variable logic on finite trees
• Complexity of two-variable logic on finite trees

Cited in

(7)

• Feasible automata for two-variable logic with successor on data words
• Small substructures and decidability issues for first-order logic with two variables
• Two-variable logic on data words
• An automaton over data words that captures EMSO logic
• Future-Looking Logics on Data Words and Trees
• Two-variable logic on data trees and XML reasoning
• Extending two-variable logic on data trees with order on data values and its automata

This page was built for publication: On the satisfiability of two-variable logic over data words

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