Two variable first-order logic over ordered domains

complexity of decision problems computation tree logic decidability finite satisfiability satisfiability problem two-variable fragment of first-order logic undecidability

Mathematics Subject Classification ID

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

Recommendations

Two-variable logic with two order relations (extended abstract)
Two-variable logic with counting and a linear order
Two variables and two successors
Decidability issues for two-variable logics with several linear orders
On the Decision Problem for Two-Variable First-Order Logic

Cites work

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

Cited in

(36)

On logics with two variables
On finite domains in first-order linear temporal logic
Decidable \({\exists}^*{\forall}^*\) first-order fragments of linear rational arithmetic with uninterpreted predicates
The light side of interval temporal logic: the Bernays-Schönfinkel fragment of CDT
An event-based fragment of first-order logic over intervals
First-order logic with two variables and unary temporal logic
Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\)
Decidability issues for two-variable logics with several linear orders
Small substructures and decidability issues for first-order logic with two variables
Two-Variable Separation Logic and Its Inner Circle
Two-variable logic on 2-dimensional structures
Optimal tableau systems for propositional neighborhood logic over all, dense, and discrete linear orders
Metric propositional neighborhood logic with an equivalence relation
Optimal Tableaux for Right Propositional Neighborhood Logic over Linear Orders
Two variables and two successors
Optimal decision procedures for MPNL over finite structures, the natural numbers, and the integers
On the expressiveness of frame satisfiability and fragments of second-order logic
Two-Variable Logic over Countable Linear Orderings
Order-invariance of two-variable logic is decidable
Satisfiability and model checking for the logic of sub-intervals under the homogeneity assumption
scientific article; zbMATH DE number 7561320 (Why is no real title available?)
Register automata with extrema constraints, and an application to two-variable logic
Finite satisfiability for two‐variable, first‐order logic with one transitive relation is decidable
Two-variable logics with some betweenness relations: expressiveness, satisfiability and membership
On the decidability of elementary modal logics
Two-variable logic with counting and trees
Two-variable logic with counting and a linear order
Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable
Two-variable logic with two order relations
Two-variable logic with two order relations (extended abstract)
Propositional interval neighborhood logics: expressiveness, decidability, and undecidable extensions
On the satisfiability of local first-order logics with data
On two-variable first-order logic with a partial order
Power domains and second-order predicates
About the expressive power and complexity of order-invariance with two variables
An optimal decision procedure for right propositional neighborhood logic

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

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