184 citations · 617 across the 22 of their papers we have counts for
20 papers · 1 filter
The Adjacent Fragment and Quine's Limits of Decision
Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
We introduce the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment gene…
On the Limits of Decision: the Adjacent Fragment of First-Order Logic
Bartosz Bednarczyk, Daumantas Kojelis, Ian Pratt-Hartmann
We define the adjacent fragment AF of first-order logic, obtained by restricting the sequences of variables occurring as arguments in atomic formulas. The adjacent fragment general…
The Fluted Fragment with Transitive Relations
Ian Pratt-Hartmann, Lidia Tendera
We study the satisfiability problem for the fluted fragment extended with transitive relations. The logic enjoys the finite model property when only one transitive relation is avai…
The Fluted Fragment with Transitivity
Ian Pratt-Hartmann, Lidia Tendera
We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive rel…
Quine's Fluted Fragment Revisited
I. Pratt-Hartmann, W. Szwast, L. Tendera
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originally identified in 1968 by W.V. Quine. We show that the satisfi…
The Finite Satisfiability Problem for Two-Variable, First-Order Logic with one Transitive Relation is Decidable
Ian Pratt-Hartmann
We consider the two-variable fragment of first-order logic with one distinguished binary predicate constrained to be interpreted as a transitive relation. The finite satisfiability…
Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting
Georgios Kourtis, Ian Pratt-Hartmann
The satisfiability and finite satisfiability problems for the two-variable guarded fragment of first-order logic with counting quantifiers, a database, and path-functional dependen…
Topological Logics with Connectedness over Euclidean Spaces
Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann +1
We consider the quantifier-free languages, Bc and Bc0, obtained by augmenting the signature of Boolean algebras with a unary predicate representing, respectively, the property of b…
The Syllogistic with Unity
Ian Pratt-Hartmann
We extend the language of the classical syllogisms with the sentence-forms "At most 1 p is a q" and "More than 1 p is a q". We show that the resulting logic does not admit a finite…
On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces
Roman Kontchakov, Yavor Nenov, Ian Pratt-Hartmann +1
We investigate (quantifier-free) spatial constraint languages with equality, contact and connectedness predicates as well as Boolean operations on regions, interpreted over low-dim…
The Hamiltonian Syllogistic
Ian Pratt-Hartmann
This paper undertakes a re-examination of Sir William Hamilton's doctrine of the quantification of the predicate. Hamilton's doctrine comprises two theses. First, the predicates of…
Spatial logics with connectedness predicates
Roman Kontchakov, Ian Pratt-Hartmann, Frank Wolter +1
We consider quantifier-free spatial logics, designed for qualitative spatial representation and reasoning in AI, and extend them with the means to represent topological connectedne…
Complex Algebras of Arithmetic
Ivo Düntsch, Ian Pratt-Hartmann
An 'arithmetic circuit' is a labeled, acyclic directed graph specifying a sequence of arithmetic and logical operations to be performed on sets of natural numbers. Arithmetic circu…
Functions Definable by Numerical Set-Expressions
Ian Pratt-Hartmann, Ivo Düntsch
A "numerical set-expression" is a term specifying a cascade of arithmetic and logical operations to be performed on sets of non-negative integers. If these operations are confined…
A Note on the Complexity of the Satisfiability Problem for Graded Modal Logics
Yevgeny Kazakov, Ian Pratt-Hartmann
Graded modal logic is the formal language obtained from ordinary (propositional) modal logic by endowing its modal operators with cardinality constraints. Under the familiar possib…
Logics for the Relational Syllogistic
Ian Pratt-Hartmann, Lawrence S. Moss
The Aristotelian syllogistic cannot account for the validity of many inferences involving relational facts. In this paper, we investigate the prospects for providing a relational s…
Data-Complexity of the Two-Variable Fragment with Counting Quantifiers
Ian Pratt-Hartmann
The data-complexity of both satisfiability and finite satisfiability for the two-variable fragment with counting is NP-complete; the data-complexity of both query-answering and fin…
On the Complexity of the Numerically Definite Syllogistic and Related Fragments
Ian Pratt-Hartmann
In this paper, we determine the complexity of the satisfiability problem for various logics obtained by adding numerical quantifiers, and other constructions, to the traditional sy…
Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
Ian Pratt-Hartmann
We show that the finite satisfiability problem for the guarded two-variable fragment with counting quantifiers is in EXPTIME. The method employed also yields a simple proof of a re…
Complexity of the Two-Variable Fragment with (Binary-Coded) Counting Quantifiers
Ian Pratt-Hartmann
We show that the satisfiability and finite satisfiability problems for the two-variable fragment of first-order logic with counting quantifiers are both in NEXPTIME, even when coun…