Ian Pratt-Hartmann
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Ian Pratt-Hartmann has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Ivo Düntsch
Brock University
3 shared publications - Lidia Tendera
Institute of Mathematics and Informatics, Opole University, Oleska 48, 45-052 Opole, Poland
3 shared publications Dominik Schoop
University of Manchester
2 shared publications- Wiesław Szwast
INSTYTUT INFORMATYKI UNIWERSYTET OPOLSKI 45-040 OPOLE, POLAND
2 shared publications - Emanuel Kieroński
University of Wroclaw
1 shared publication - Lidia Tendera
University of Opole, Institute of Computer Science, Oleska 48, 45-052 Opole, Poland
1 shared publication
Latest Publications
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 476-543
Equivalence and counting
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.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 476-543
Equivalence and counting
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.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 148-186
Prefixes
We consider fragments of first-order logic (with and without equality) defined by means of standard quantifier prefix specifiers, over signatures containing no function symbols. We determine, in each case, the decidability and complexity of the (finite) satisfiability problem. Two of these results tower above the others. The first concerns the so-called Gödel fragment, where the quantifier prefix features two adjacent universal quantifiers and at least one trailing existential quantifier, but where equality is not allowed. We show that this fragment has the finite model property, and that its satisfiability problem is NExpTime-complete. The second concerns the so-called Goldfarb fragment, which adds equality to the Gödel fragment. We show that the satisfiability and finite satisfiability problems for this fragment are undecidable. We also discuss the effect on lower complexity bounds of making individual constants unavailable.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 148-186
Prefixes
We consider fragments of first-order logic (with and without equality) defined by means of standard quantifier prefix specifiers, over signatures containing no function symbols. We determine, in each case, the decidability and complexity of the (finite) satisfiability problem. Two of these results tower above the others. The first concerns the so-called Gödel fragment, where the quantifier prefix features two adjacent universal quantifiers and at least one trailing existential quantifier, but where equality is not allowed. We show that this fragment has the finite model property, and that its satisfiability problem is NExpTime-complete. The second concerns the so-called Goldfarb fragment, which adds equality to the Gödel fragment. We show that the satisfiability and finite satisfiability problems for this fragment are undecidable. We also discuss the effect on lower complexity bounds of making individual constants unavailable.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 280-324
Guarded counting
We consider the guarded two-variable fragment of first-order logic with counting quantifiers, a subfragment of the two-variable fragment with counting quantifiers in which, in addition to the requirement of guarding, individual constants do not appear. We show that this logic lacks the finite model property, but that its satisfiability and finite satisfiability problems are both nevertheless ExpTime-complete. We introduce the concepts of database and data complexity, and show that the satisfiability and finite satisfiability problems for the guarded two-variable fragment of first-order logic with counting quantifiers and databases remain in ExpTime, and are NPTime-complete for data-complexity.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 280-324
Guarded counting
We consider the guarded two-variable fragment of first-order logic with counting quantifiers, a subfragment of the two-variable fragment with counting quantifiers in which, in addition to the requirement of guarding, individual constants do not appear. We show that this logic lacks the finite model property, but that its satisfiability and finite satisfiability problems are both nevertheless ExpTime-complete. We introduce the concepts of database and data complexity, and show that the satisfiability and finite satisfiability problems for the guarded two-variable fragment of first-order logic with counting quantifiers and databases remain in ExpTime, and are NPTime-complete for data-complexity.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 67-103
Variables
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.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 67-103
Variables
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.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 325-370
Omitting graphs
We introduce the concepts of conjunctive query and (finite) query answering, and show that the problems of query answering and finite query answering in the guarded two-variable fragment of first-order logic with counting quantifiers and databases are in 2-ExpTime, falling to co-NPTime for data complexity. We also consider the extension of this fragment with key constraints, and show that the complexity of the (finite) satisfiability and (finite) query-answering problems does not increase.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 325-370
Omitting graphs
We introduce the concepts of conjunctive query and (finite) query answering, and show that the problems of query answering and finite query answering in the guarded two-variable fragment of first-order logic with counting quantifiers and databases are in 2-ExpTime, falling to co-NPTime for data complexity. We also consider the extension of this fragment with key constraints, and show that the complexity of the (finite) satisfiability and (finite) query-answering problems does not increase.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 427-475
Equivalence
We consider the two-variable fragment of first-order logic, but where k distinguished binary predicates are constrained to be interpreted as equivalence relations. We show that, if k=1, the resulting logic has the finite model property, and that the satisfiability problem remains NExpTime-complete. We further show that, if k=2, the resulting logic loses the finite model property, and that the satisfiability and finite satisfiability problems become 2-NExpTime-complete. Finally, we show that, if k=3, the satisfiability and finite satisfiability problems for the resulting logic become undecidable.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 427-475
Equivalence
We consider the two-variable fragment of first-order logic, but where k distinguished binary predicates are constrained to be interpreted as equivalence relations. We show that, if k=1, the resulting logic has the finite model property, and that the satisfiability problem remains NExpTime-complete. We further show that, if k=2, the resulting logic loses the finite model property, and that the satisfiability and finite satisfiability problems become 2-NExpTime-complete. Finally, we show that, if k=3, the satisfiability and finite satisfiability problems for the resulting logic become undecidable.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 225-250
Counting with one variable
This chapter introduces the notion of counting quantifiers, and presents some fundamental results in the theory of integer linear programming. We explain the notion of the minimal basis of an integer linear programming instance, and obtain bounds on the values occurring in it. We also introduce the notion of the footprint of a solution, and obtain an upper bound on its cardinality. These results will be used throughout the remainder of the book. In the present chapter, they enable us to show that the one-variable fragment of first-order logic with counting quantifiers has the finite model property, and that its satisfiability problem is in NPTime. We additionally consider the numerical syllogistic, a subfragment of the one-variable fragment with counting quantifiers, originally investigated by A. De Morgan. We show that its satisfiability problem is NPTime-hard.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 225-250
Counting with one variable
This chapter introduces the notion of counting quantifiers, and presents some fundamental results in the theory of integer linear programming. We explain the notion of the minimal basis of an integer linear programming instance, and obtain bounds on the values occurring in it. We also introduce the notion of the footprint of a solution, and obtain an upper bound on its cardinality. These results will be used throughout the remainder of the book. In the present chapter, they enable us to show that the one-variable fragment of first-order logic with counting quantifiers has the finite model property, and that its satisfiability problem is in NPTime. We additionally consider the numerical syllogistic, a subfragment of the one-variable fragment with counting quantifiers, originally investigated by A. De Morgan. We show that its satisfiability problem is NPTime-hard.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 544-599
Transitivity
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.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 544-599
Transitivity
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.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 187-222
Fluting
We consider the so-called fluted fragment, a fragment of first-order logic originating in the work of W.V.O. Quine in which, roughly speaking, the order of quantification of variables is constrained to match the order of occurrence of those variables in atomic formulas. We show that this fragment has the finite model property, and that its satisfiability problem is decidable, but with non-elementary complexity. We also determine, within certain bounds, the complexity of satisfiability for the k-variable subfragment, for all k.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 187-222
Fluting
We consider the so-called fluted fragment, a fragment of first-order logic originating in the work of W.V.O. Quine in which, roughly speaking, the order of quantification of variables is constrained to match the order of occurrence of those variables in atomic formulas. We show that this fragment has the finite model property, and that its satisfiability problem is decidable, but with non-elementary complexity. We also determine, within certain bounds, the complexity of satisfiability for the k-variable subfragment, for all k.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 373-426
Modalities
We explain how propositional modal logics can be understood as subfragments of the two-variable fragment of first-order logic, in which the interpretation of a distinguished binary relation is subject to various semantic constraints, in particular, the properties of reflexivity, seriality, symmetry and transitivity. We introduce graded modal logic, which extends propositional modal logics (thus understood) with counting quantifiers. We determine the complexity of the satisfiability problems for modal logics and graded modal logics defined by all possible conjunctions of the semantic constraints just mentioned. We also characterize the expressive power of propositional modal logic and briefly consider some extensions contained within the two-variable fragment of first-order logic.
- 30 March 2023
- Published by Oxford University Press (OUP)
- p. 373-426
Modalities
We explain how propositional modal logics can be understood as subfragments of the two-variable fragment of first-order logic, in which the interpretation of a distinguished binary relation is subject to various semantic constraints, in particular, the properties of reflexivity, seriality, symmetry and transitivity. We introduce graded modal logic, which extends propositional modal logics (thus understood) with counting quantifiers. We determine the complexity of the satisfiability problems for modal logics and graded modal logics defined by all possible conjunctions of the semantic constraints just mentioned. We also characterize the expressive power of propositional modal logic and briefly consider some extensions contained within the two-variable fragment of first-order logic.