Two variable first-order logic over ordered domains

DOI10.2307/2695037zbMath0990.03005OpenAlexW2104419987MaRDI QIDQ2747711

Martin Otto

Publication date: 25 July 2002

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2307/2695037

zbMATH Keywords

undecidabilitydecidabilitysatisfiability problemcomputation tree logicfinite satisfiabilitycomplexity of decision problemstwo-variable fragment of first-order logic

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (19)

On the Decidability of Elementary Modal Logics ⋮ Two-Variable Logic with Counting and Trees ⋮ Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\) ⋮ Metric propositional neighborhood logic with an equivalence relation ⋮ Small substructures and decidability issues for first-order logic with two variables ⋮ An optimal decision procedure for right propositional neighborhood logic ⋮ Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers ⋮ Two-Variable Separation Logic and Its Inner Circle ⋮ Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable ⋮ An event-based fragment of first-order logic over intervals ⋮ Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions ⋮ Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders ⋮ Unnamed Item ⋮ Optimal Tableau Systems for Propositional Neighborhood Logic over All, Dense, and Discrete Linear Orders ⋮ The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates ⋮ Unnamed Item

Cites Work

• Undecidability results on two-variable logics
• On logics with two variables
• Remarks on Berger's paper on the domino problem
• On languages with two variables
• On the Decision Problem for Two-Variable First-Order Logic

This page was built for publication: Two variable first-order logic over ordered domains