David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Journal of Symbolic Logic 66 (2):685-702 (2001)
The satisfiability problem for the two-variable fragment of first-order logic is investigated over finite and infinite linearly ordered, respectively wellordered domains, as well as over finite and infinite domains in which one or several designated binary predicates are interpreted as arbitrary wellfounded relations. It is shown that FO 2 over ordered, respectively wellordered, domains or in the presence of one well-founded relation, is decidable for satisfiability as well as for finite satisfiability. Actually the complexity of these decision problems is essentially the same as for plain unconstrained FO 2 , namely non-deterministic exponential time. In contrast FO 2 becomes undecidable for satisfiability and for finite satisfiability, if a sufficiently large number of predicates are required to be interpreted as orderings, wellorderings, or as arbitrary wellfounded relations. This undecidability result also entails the undecidability of the natural common extension of FO 2 and computation tree logic CTL
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
William C. Purdy (2002). Complexity and Nicety of Fluted Logic. Studia Logica 71 (2):177 - 198.
Ian Pratt-Hartmann (2008). On the Computational Complexity of the Numerically Definite Syllogistic and Related Logics. Bulletin of Symbolic Logic 14 (1):1-28.
Savas Konur (2011). An Event-Based Fragment of First-Order Logic Over Intervals. Journal of Logic, Language and Information 20 (1):49-68.
Thomas Eiter & Georg Gottlob (1998). On the Expressiveness of Frame Satisfiability and Fragments of Second-Order Logic. Journal of Symbolic Logic 63 (1):73-82.
Stéphane Demri & Hans De Nivelle (2005). Deciding Regular Grammar Logics with Converse Through First-Order Logic. Journal of Logic, Language and Information 14 (3):289-329.
Roman Kontchakov, Agi Kurucz & Michael Zakharyaschev (2005). Undecidability of First-Order Intuitionistic and Modal Logics with Two Variables. Bulletin of Symbolic Logic 11 (3):428-438.
Erich Grädel (1999). On the Restraining Power of Guards. Journal of Symbolic Logic 64 (4):1719-1742.
Ian Hodkinson (2002). Monodic Packed Fragment with Equality is Decidable. Studia Logica 72 (2):185-197.
Ian Pratt-Hartmann (2005). Complexity of the Two-Variable Fragment with Counting Quantifiers. Journal of Logic, Language and Information 14 (3):369-395.
Erich Grädel, Phokion G. Kolaitis & Moshe Y. Vardi (1997). On the Decision Problem for Two-Variable First-Order Logic. Bulletin of Symbolic Logic 3 (1):53-69.
Added to index2009-01-28
Total downloads5 ( #175,692 of 1,003,359 )
Recent downloads (6 months)0
How can I increase my downloads?