IPIan Pratt-Hartmann

Ian Pratt-Hartmann

*This is an algorithmically generated author record based on publicly available information.

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:


Latest Publications

  • Equivalence and counting

    by Ian Pratt-Hartmann

    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.

  • Prefixes

    by Ian Pratt-Hartmann

    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.

  • Guarded counting

    by Ian Pratt-Hartmann

    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.

  • Variables

    by Ian Pratt-Hartmann

    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.

  • Omitting graphs

    by Ian Pratt-Hartmann

    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.

  • Equivalence

    by Ian Pratt-Hartmann

    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.

  • Counting with one variable

    by Ian Pratt-Hartmann

    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.

  • Transitivity

    by Ian Pratt-Hartmann

    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.

  • Fluting

    by Ian Pratt-Hartmann

    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.

  • Modalities

    by Ian Pratt-Hartmann

    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.