Variables
- 30 March 2023
- book chapter
- Published by Oxford University Press (OUP)
- p. 67-103
Abstract
We consider the two-variable fragment of first-order logic, showing that it has the finite model property, and that its satisfiability problem is in NExpTime. We introduce the technique of reduction to the infinite tiling problem, and use it to show that the satisfiability and finite satisfiability problems for the three-variable fragment of first-order logic are both undecidable. We then introduce the technique of reduction to bounded tiling problems and use it to show that the satisfiability problem for the two-variable fragment of first-order logic is NExpTime-hard. We also consider the monadic fragment of first-order logic, and show that its satisfiability problem is also NExpTime-complete. Finally we obtain a semantic characterization of the expressive power of the k-variable fragment of first-order logic.Keywords
This publication has 32 references indexed in Scilit:
- Complexity of Two-Variable Logic on Finite TreesLecture Notes in Computer Science, 2013
- No Syllogisms for the Numerical SyllogisticLecture Notes in Computer Science, 2009
- The Complexity of Conjunctive Query Answering in Expressive Description LogicsLecture Notes in Computer Science, 2008
- Towards Efficient Satisfiability Checking for Boolean Algebra with Presburger Arithmetic2007
- A Polynomial Translation from the Two-Variable Guarded Fragment with Number Restrictions to the Guarded FragmentLecture Notes in Computer Science, 2004
- Resolution Decision Procedures2001
- Resolution Theorem Proving2001
- Translating Graded Modalities into Predicate Logics1996
- A bound on solutions of linear integer equalities and inequalitiesProceedings of the American Mathematical Society, 1978
- Bounds on positive integral solutions of linear Diophantine equationsProceedings of the American Mathematical Society, 1976