Pratt-Hartmann considers for which fragments of first-order logic there is an effective method for determining satisfiability or finite satisfiability. Furthermore, he asks, if these problems are decidable for some fragment, what is their computational complexity?

Ian Pratt-Hartmann studied mathematics and philosophy at Brasenose College, Oxford, and philosophy at Princeton and Stanford Universities, gaining his PhD from Princeton in 1987. He is currently Senior Lecturer in the Department of Computer Science at the University of Manchester as well as Professor of Mathematical Sciences in the Institute of Computer Science at the University of Opole, and recently held an appointment as Visiting Professor at the Department of Mathematics, Computer Science and Mechanics at the University of Warsaw.

• Preface


• Acknowledgements


• 1: Introduction


• Part I: Syntactic Restrictions


• 2: Roots


• 3: Variables


• 4: Guards


• 5: Prefixes


• 6: Fluting


• Part II: Counting Quantifiers


• 7: Counting with one variable


• 8: Counting with two variables


• 9: Guarded counting


• 10: Omitting graphs


• Part III: Semantic Constraints


• 11: Modalities


• 12: Equivalence


• 13: Equivalence and counting


• 14: Transitivity


• 15: Trees