John Grant

JAAMAS Journal 2026 Journal Article

A Logic for Characterizing Multiple Bounded Agents

• John Grant
• Sarit Kraus
• Donald Perlis

Abstract We describe a meta-logic for characterizing the evolving internal reasoning of various families of agents. We view the reasoning of agents as ongoing processes rather than as fixed sets of conclusions. Our approach utilizes a strongly sorted calculus, distinguishing the application language, time, and various syntactic sorts. We have established soundness and completeness results corresponding to various families of agents. This allows for useful and intuitively natural characterizations of such agents' reasoning abilities. We discuss and contrast consistency issues as in the work of Montague and Thomason. We also show how to represent the concept of focus of attention in this framework.

IJCAI Conference 2025 Conference Paper

On Measuring Inconsistency in Graph Databases with Regular Path Constraints (Abstract Reprint)

• John Grant
• Francesco Parisi

Real-world data are often inconsistent. Although a substantial amount of research has been done on measuring inconsistency, this research concentrated on knowledge bases formalized in propositional logic. Recently, inconsistency measures have been introduced for relational databases. However, nowadays, real-world information is always more frequently represented by graph-based structures which offer a more intuitive conceptualization than relational ones. In this paper, we explore inconsistency measures for graph databases with regular path constraints, a class of integrity constraints based on a well-known navigational language for graph data. In this context, we define several inconsistency measures dealing with specific elements contributing to inconsistency in graph databases. We also define some rationality postulates that are desirable properties for an inconsistency measure for graph databases. We analyze the compliance of each measure with each postulate and find various degrees of satisfaction; in fact, one of the measures satisfies all the postulates. Finally, we investigate the data and combined complexity of the calculation of all the measures as well as the complexity of deciding whether a measure is lower than, equal to, or greater than a given threshold. It turns out that for a majority of the measures these problems are tractable, while for the other different levels of intractability are exhibited.

AIJ Journal 2024 Journal Article

On measuring inconsistency in graph databases with regular path constraints

• John Grant
• Francesco Parisi

Real-world data are often inconsistent. Although a substantial amount of research has been done on measuring inconsistency, this research concentrated on knowledge bases formalized in propositional logic. Recently, inconsistency measures have been introduced for relational databases. However, nowadays, real-world information is always more frequently represented by graph-based structures which offer a more intuitive conceptualization than relational ones. In this paper, we explore inconsistency measures for graph databases with regular path constraints, a class of integrity constraints based on a well-known navigational language for graph data. In this context, we define several inconsistency measures dealing with specific elements contributing to inconsistency in graph databases. We also define some rationality postulates that are desirable properties for an inconsistency measure for graph databases. We analyze the compliance of each measure with each postulate and find various degrees of satisfaction; in fact, one of the measures satisfies all the postulates. Finally, we investigate the data and combined complexity of the calculation of all the measures as well as the complexity of deciding whether a measure is lower than, equal to, or greater than a given threshold. It turns out that for a majority of the measures these problems are tractable, while for the other different levels of intractability are exhibited.

NMR Workshop 2023 Conference Paper

An ASP-Based Framework for Solving Problems Related to Declarative Process Specifications

• Isabelle Kuhlmann
• Carl Corea
• John Grant

We present a framework of answer set programming-based solutions for various problems related to declarative process specifications. Specifically, the framework offers implementations for conformance checking, satisfiability checking, and two different inconsistency measures. Since the aforementioned problems are represented in a fragment of linear temporal logic, the framework could also prove useful for a broader range of applications beyond process specifications.

AIJ Journal 2023 Journal Article

On measuring inconsistency in definite and indefinite databases with denial constraints

• Francesco Parisi
• John Grant

Real-world databases are often inconsistent. Although there has been an extensive body of work on handling inconsistency, little work has been done on measuring inconsistency in databases. In this paper, building on work done on measuring inconsistency in propositional knowledge bases, we explore inconsistency measures (IMs) for definite and indefinite databases with denial constraints. We first introduce database IMs that are inspired by well-established methods to quantify inconsistency in propositional knowledge bases, but are tailored to the relational database context where data is generally the reason for inconsistency, not the integrity constraints. Then, we analyze the compliance of the database IMs with rationality postulates for both definite and indefinite databases. Finally, we investigate the complexity of the inconsistency measurement problem as well as of the problems of deciding whether the inconsistency is lower than, greater than, or equal to a given threshold for both the definite and the indefinite cases.

IJCAI Conference 2023 Conference Paper

Relative Inconsistency Measures for Indefinite Databases with Denial Constraints

• Francesco Parisi
• John Grant

Handling conflicting information is an important challenge in AI. Measuring inconsistency is an approach that provides ways to quantify the severity of inconsistency and helps understanding the primary sources of conflicts. In particular, a relative inconsistency measure computes, by some criteria, the proportion of the knowledge base that is inconsistent. In this paper we investigate relative inconsistency measures for indefinite databases, which allow for indefinite or partial information which is formally expressed by means of disjunctive tuples. We introduce a postulate-based definition of relative inconsistency measure for indefinite databases with denial constraints, and investigate the compliance of some relative inconsistency measures with rationality postulates for indefinite databases as well as for the special case of definite databases. Finally, we investigate the complexity of the problem of computing the value of the proposed relative inconsistency measures as well as of the problems of deciding whether the inconsistency value is lower than, greater than, or equal to a given threshold for indefinite and definite databases.

IJCAI Conference 2022 Conference Paper

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases (Extended Abstract)

• John Grant
• Maria Vanina Martinez
• Cristian Molinaro
• Francesco Parisi

We define and investigate new inconsistency measures that are particularly suitable for dealing with inconsistent spatio-temporal information, as they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w. r. t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions, and thus define ``dimension-aware'' counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

JAIR Journal 2021 Journal Article

Dimensional Inconsistency Measures and Postulates in Spatio-Temporal Databases

• John Grant
• Maria Vanina Martinez
• Cristian Molinaro
• Francesco Parisi

The problem of managing spatio-temporal data arises in many applications, such as location-based services, environmental monitoring, geographic information systems, and many others. Often spatio-temporal data arising from such applications turn out to be inconsistent, i.e., representing an impossible situation in the real world. Though several inconsistency measures have been proposed to quantify in a principled way inconsistency in propositional knowledge bases, little effort has been done so far on inconsistency measures tailored for the spatio-temporal setting. In this paper, we define and investigate new measures that are particularly suitable for dealing with inconsistent spatio-temporal information, because they explicitly take into account the spatial and temporal dimensions, as well as the dimension concerning the identifiers of the monitored objects. Specifically, we first define natural measures that look at individual dimensions (time, space, and objects), and then propose measures based on the notion of a repair. We then analyze their behavior w.r.t. common postulates defined for classical propositional knowledge bases, and find that the latter are not suitable for spatio-temporal databases, in that the proposed inconsistency measures do not often satisfy them. In light of this, we argue that also postulates should explicitly take into account the spatial, temporal, and object dimensions and thus define “dimension-aware” counterparts of common postulates, which are indeed often satisfied by the new inconsistency measures. Finally, we study the complexity of the proposed inconsistency measures.

FLAP Journal 2020 Journal Article

Measuring Inconsistency in Finitary First-order Logic.

• John Grant

Since the early 2000s, researchers in logic and AI have developed a framework for measuring inconsistency in information. They proposed inconsistency measures as well as desirable properties for them and dealt with related issues. AI researchers are interested in this topic because some intelligent systems need to handle inconsistencies. However, the bulk of the research has been done for propositional knowledge bases, that is, finite sets of formulas in propositional logic. But much of the information that intelligent systems deal with, such as databases, use first-order logic formulas. The purpose of this paper is to extend inconsistency measuring to finite sets of first-order logic formulas. We propose five different measures and explain the rationale for each. Furthermore, we extend some of the properties proposed for propositional inconsistency measures to first-order logic and introduce several new properties appropriate for firstorder logic. We show the satisfaction or violation of each property for each measure.

ECAI Conference 2020 Conference Paper

On Measuring Inconsistency in Relational Databases with Denial Constraints

• Francesco Parisi
• John Grant

Real-world databases are often inconsistent. Although there has been an extensive body of work on handling inconsistency, little work has been done on measuring inconsistency in databases. In this paper, building on work done on measuring inconsistency in propositional knowledge bases, we explore inconsistency measures (IMs) for databases with denial constraints. We first introduce new database IMs that are inspired by well-established methods to quantify inconsistency in propositional knowledge bases, but are tailored to the relational database context where data are generally the reason for inconsistency, not the integrity constraints. Then, we analyze the compliance of the database IMs with rationality postulates, and investigate the complexity of the inconsistency measurement problem as well as of the problems of deciding whether the inconsistency is lower than, greater than, or equal to a given threshold.

AIJ Journal 2020 Journal Article

Relative inconsistency measures

• Philippe Besnard
• John Grant

The literature on inconsistency measures has ignored a distinction, that is, differentiating absolute measures and relative measures. An absolute measure gives the total amount of inconsistency in the knowledge base but a relative measure computes, by some criteria, the proportion of the base that is inconsistent. To compare the inconsistency measures, researchers have proposed postulates for such measures. We split these postulates into three groups: ones (including two new postulates) that relative measures should satisfy, ones inappropriate for relative measures, and ones that relative measures may satisfy. We obtain some new results upon the relationships between these groups of postulates. On these grounds, we introduce a formal definition for relative inconsistency measures. We consider some relative measures previously proposed and define several new ones that serve as examples. We show that all of these measures satisfy the new formal definition.

JAIR Journal 2019 Journal Article

Classifying Inconsistency Measures Using Graphs

• Glauber de Bona
• John Grant
• Anthony Hunter
• Sebastien Konieczny

The aim of measuring inconsistency is to obtain an evaluation of the imperfections in a set of formulas, and this evaluation may then be used to help decide on some course of action (such as rejecting some of the formulas, resolving the inconsistency, seeking better sources of information, etc). A number of proposals have been made to define measures of inconsistency. Each has its rationale. But to date, it is not clear how to delineate the space of options for measures, nor is it clear how we can classify measures systematically. To address these problems, we introduce a general framework for comparing syntactic measures of inconsistency. It is based on the notion of an inconsistency graph for each knowledgebase (a bipartite graph with a set of vertices representing formulas in the knowledgebase, a set of vertices representing minimal inconsistent subsets of the knowledgebase, and edges representing that a formula belongs to a minimal inconsistent subset). We then show that various measures can be computed using the inconsistency graph. Then we introduce abstractions of the inconsistency graph and use them to construct a hierarchy of syntactic inconsistency measures. Furthermore, we extend the inconsistency graph concept with a labeling that extends the hierarchy to include some other types of inconsistency measures.

AAAI Conference 2018 Conference Paper

Towards a Unified Framework for Syntactic Inconsistency Measures

• Glauber de Bona
• John Grant
• Anthony Hunter
• Sébastien Konieczny

A number of proposals have been made to define inconsistency measures. Each has its rationale. But to date, it is not clear how to delineate the space of options for measures, nor is it clear how we can classify measures systematically. In this paper, we introduce a general framework for comparing syntactic inconsistency measures. It uses the construction of an inconsistency graph for each knowledgebase. We then introduce abstractions of the inconsistency graph and use the hierarchy of the abstractions to classify a range of inconsistency measures.

JAIR Journal 2016 Journal Article

Knowledge Representation in Probabilistic Spatio-Temporal Knowledge Bases

• Francesco Parisi
• John Grant

We represent knowledge as integrity constraints in a formalization of probabilistic spatio-temporal knowledge bases. We start by defining the syntax and semantics of a formalization called PST knowledge bases. This definition generalizes an earlier version, called SPOT, which is a declarative framework for the representation and processing of probabilistic spatio-temporal data where probability is represented as an interval because the exact value is unknown. We augment the previous definition by adding a type of non-atomic formula that expresses integrity constraints. The result is a highly expressive formalism for knowledge representation dealing with probabilistic spatio-temporal data. We obtain complexity results both for checking the consistency of PST knowledge bases and for answering queries in PST knowledge bases, and also specify tractable cases. All the domains in the PST framework are finite, but we extend our results also to arbitrarily large finite domains.

IJCAI Conference 2011 Conference Paper

Manipulating Boolean Games through Communication

• John Grant
• Sarit Kraus
• Michael Wooldridge
• Inon Zuckerman

We address the issue of manipulating games through communication. In the specific setting we consider (a variation of Boolean games), we assume there is some set of environment variables, the value of which is not directly accessible to players; each player has their own beliefs about these variables, and makes decisions about what actions to perform based on these beliefs. The communication we consider takes the form of (truthful) announcements about the value of some environment variables; the effect of an announcement about some variable is to modify the beliefs of the players who hear the announcement so that they accurately reflect the value of the announced variables. By choosing announcements appropriately, it is possible to perturb the game away from certain rational outcomes and towards others. We specifically focus on the issue of stabilisation: making announcements that transform a game from having no stable states to one that has stable configurations.

IJCAI Conference 2011 Conference Paper

Measuring the Good and the Bad in Inconsistent Information

• John Grant
• Anthony Hunter

There is interest in artificial intelligence for principled techniques to analyze inconsistent information. This stems from the recognition that the dichotomy between consistent and inconsistent sets of formulae that comes from classical logics is not sufficient for describing inconsistent information. We review some existing proposals and make new proposals for measures of inconsistency and measures of information, and then prove that they are all pairwise incompatible. This shows that the notion of inconsistency is a multi-dimensional concept where different measures provide different insights. We then explore relationships between measures of inconsistency and measures of information in terms of the trade-offs they identify when using them to guide resolution of inconsistency.

AIJ Journal 2010 Journal Article

An AGM-style belief revision mechanism for probabilistic spatio-temporal logics

• John Grant
• Francesco Parisi
• Austin Parker
• V.S. Subrahmanian

There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form “Object o is/was/will be in region r at time t with probability in the interval [ ℓ, u ] ”. In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.

AAAI Conference 2010 Conference Paper

Intentions in Equilibrium

• John Grant
• Sarit Kraus
• Michael Wooldridge

Intentions have been widely studied in AI, both in the context of decision-making within individual agents and in multiagent systems. Work on intentions in multi-agent systems has focused on joint intention models, which characterise the mental state of agents with a shared goal engaged in teamwork. In the absence of shared goals, however, intentions play another crucial role in multi-agent activity: they provide a basis around which agents can mutually coordinate activities. Models based on shared goals do not attempt to account for or explain this role of intentions. In this paper, we present a formal model of multi-agent systems in which belief-desire-intention agents choose their intentions taking into account the intentions of others. To understand rational mental states in such a setting, we formally define and investigate notions of multi-agent intention equilibrium, which are related to equilibrium concepts in game theory.

AIJ Journal 2008 Journal Article

Active logic semantics for a single agent in a static world

• Michael L. Anderson
• Walid Gomaa
• John Grant
• Don Perlis

For some time we have been developing, and have had significant practical success with, a time-sensitive, contradiction-tolerant logical reasoning engine called the active logic machine (ALMA). The current paper details a semantics for a general version of the underlying logical formalism, active logic. Central to active logic are special rules controlling the inheritance of beliefs in general (and of beliefs about the current time in particular), very tight controls on what can be derived from direct contradictions ( P & ¬ P ), and mechanisms allowing an agent to represent and reason about its own beliefs and past reasoning. Furthermore, inspired by the notion that until an agent notices that a set of beliefs is contradictory, that set seems consistent (and the agent therefore reasons with it as if it were consistent), we introduce an “apperception function” that represents an agent's limited awareness of its own beliefs, and serves to modify inconsistent belief sets so as to yield consistent sets. Using these ideas, we introduce a new definition of logical consequence in the context of active logic, as well as a new definition of soundness such that, when reasoning with consistent premises, all classically sound rules remain sound in our new sense. However, not everything that is classically sound remains sound in our sense, for by classical definitions, all rules with contradictory premises are vacuously sound, whereas in active logic not everything follows from a contradiction.

AIJ Journal 2008 Journal Article

Analysing inconsistent first-order knowledgebases

• John Grant
• Anthony Hunter

It is well-known that knowledgebases may contain inconsistencies. We provide a framework of measures, based on a first-order four-valued logic, to quantify the inconsistency of a knowledgebase. This allows for the comparison of the inconsistency of diverse knowledgebases that have been represented as sets of first-order logic formulae. We motivate the approach by considering some examples of knowledgebases for representing and reasoning with ontological knowledge and with temporal knowledge. Analysing ontological knowledge (including the statements about which concepts are subconcepts of other concepts, and which concepts are disjoint) can be problematical when there is a lack of knowledge about the instances that may populate the concepts, and analysing temporal knowledge (such as temporal integrity constraints) can be problematical when considering infinite linear time lines isomorphic to the natural numbers or the real numbers or more complex structures such as branching time lines. We address these difficulties by providing algebraic measures of inconsistency in first-order knowledgebases.

AIJ Journal 2005 Journal Article

A logic-based model of intention formation and action for multi-agent subcontracting

• John Grant
• Sarit Kraus
• Donald Perlis

We present a formalism for representing the formation of intentions by agents engaged in cooperative activity. We use a syntactic approach presenting a formal logical calculus that can be regarded as a meta-logic that describes the reasoning and activities of the agents. Our central focus is on the evolving intentions of agents over time, and the conditions under which an agent can adopt and maintain an intention. In particular, the reasoning time and the time taken to subcontract are modeled explicitly in the logic. We axiomatize the concept of agent interactions in the meta-language, show that the meta-theory is consistent and describe the unique intended model of the meta-theory. In this context we deal both with subcontracting between agents and the presence of multiple recipes, that is, multiple ways of accomplishing tasks. We show that under various initial conditions and known facts about agent beliefs and abilities, the meta-theory representation yields good results.

AAAI Conference 2002 Conference Paper

A Logic-Based Model of Intentions for Multi-Agent Subcontracting

• John Grant
• Bar-Ilan University and University of Maryland; Donald Perlis

We present a formalism for representing the intentions of agents engaged in cooperative planning and acting. We focus on cases where one agent alone cannot accomplish a complex task and must subcontract with other agents. Evolving intentions over time during the planning and acting, and the conditions under which an agent can adopt and maintain an intention, are central. In particular, the time taken to plan and to subcontract are modeled explicitly in the logic. This explicit time-representation is used to account for the time it takes an agent to adopt an intention. We use a syntactic approach presenting a formal logical calculus that can be regarded as a meta-logic that describes the reasoning and activities of the agents. We write some of the axioms of this metalanguage and explain the minimal model semantics, in which one model, the intended model, represents the actual beliefs, intentions, and actions of the agents. We also prove several results showing that under the appropriate conditions the agents will act as expected.

KER Journal 1992 Journal Article

On object-orieted database systems by K. R. Dittrich, U. Dayal and A. P. Buchmann (Eds.), Springer-Verlag, Berlin, 1991, pp. 422 (hardcover), DM98, ISBN 0-387 53496-2.

• John Grant

KER Journal 1989 Journal Article

Deductive database theories

• John Grant
• Jack Minker

Abstract This paper surveys a variety of deductive database theories. Such theories differ from one another in the set of axioms and metarules that they allow and use. The following theories are discussed: relational, Horn, and stratified in the text; protected, disjunctive, typed, extended Horn, and normal in the appendix. Connections with programming in terms of the declarative, fixpoint, and procedural semantics are explained. Negation is treated in several different ways: closed world, completed database, and negation as failure. For each theory examples are given and implementation issues are considered.

TCS Journal 1985 Journal Article

Inferences for numerical dependencies

• John Grant
• Jack Minker

We introduce and motivate the study of numerical dependencies which are a generalization of functional dependencies. We prove that there does not exist a finite set of sound and complete inference rules for numerical dependencies in contrast to the case of functional dependencies. We also prove that nontrivial numerical dependencies which are not functional dependencies cannot be expressed by Horn formulas in first-order logic, and show some applications of numerical dependencies.