Transitivity
- 30 March 2023
- book chapter
- Published by Oxford University Press (OUP)
- p. 544-599
Abstract
We consider the two-variable fragment of first-order logic with counting quantifiers, but where k distinguished binary predicates are constrained to be interpreted as equivalence relations. We show that, if k=1, the satisfiability and finite satisfiability problems for the resulting logic remain NExpTime-complete. Our treatment here employs the full power of the results on integer linear programming obtained in Chapter 7. In addition, we show that, if k=2, the satisfiability and finite satisfiability problems for the resulting logic become undecidable.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