Thomas Meyer

KR Conference 2025 Conference Paper

An Analysis of the Role of Syntax in Inductive Inference

• Jesse Heyninck
• Richard Booth
• Thomas Meyer
• Lars-Phillip Spiegel

Inductive inference is a well-studied form of nonmonotonic reasoning in which various inference is based on conditional belief bases rather than belief bases consisting of classical logic statements. Given its nonmonotonic nature, many important logical properties that are taken for granted in the classical case do not necessarily carry over to inference involving conditionals. In this paper we consider two such properties---equivalence and language-independence. More specifically, we provide different notions of equivalence in the conditional case, and show which of these are satisfied by which forms of conditional inference. Similarly, we consider different versions of language independence, and test various forms of conditional inference against these. As its main overall contribution, the paper provides deeper theoretical insights into the field of inductive inference.

KR Conference 2025 Conference Paper

Reasoning in Defeasible Description Logics with System W and Lexicographic Inference

• Giovanni Casini
• Jonas Haldimann
• Thomas Meyer

Description Logics (DLs) are widely applied in AI and database systems. However, like other classical logics, they cannot adequately handle defeasible information. Building on the notion of rational closure - a form of defeasible reasoning originally developed for the propositional setting and later adapted to DLs - we extend this approach by incorporating two further forms of defeasible reasoning: System W and lexicographic closure. Both are well-established entailment relations in the propositional case and are known to satisfy several desirable properties. In this paper, we provide model-theoretic definitions of these extensions for DLs, analyze their behaviour by relating them to their propositional counterparts, and present algorithms for their computation.

AAAI Conference 2023 Conference Paper

Conditional Syntax Splitting for Non-monotonic Inference Operators

• Jesse Heyninck
• Gabriele Kern-Isberner
• Thomas Meyer
• Jonas Philipp Haldimann
• Christoph Beierle

Syntax splitting is a property of inductive inference operators that ensures we can restrict our attention to parts of the conditional belief base that share atoms with a given query. To apply syntax splitting, a conditional belief base needs to consist of syntactically disjoint conditionals. This requirement is often too strong in practice, as conditionals might share atoms. In this paper we introduce the concept of conditional syntax splitting, inspired by the notion of conditional independence as known from probability theory. We show that lexicographic inference and system W satisfy conditional syntax splitting, and connect conditional syntax splitting to several known properties from the literature on non-monotonic reasoning, including the drowning effect.

FLAP Journal 2023 Journal Article

Do Humans Find Postulates of Belief Change Plausible?

• Clayton Kevin Baker
• Thomas Meyer

Various empirical methods were used to test whether humans agree with pos- tulates of non-monotonic reasoning and belief change. This work investigates through surveys whether postulates of revision and update are plausible with human reasoners when presented as material implication statements. We used statistical methods to measure the association between the antecedent and the consequent of each postulate. The results show that participants tend to find postulates of update more plausible than postulates of revision.

KR Conference 2023 Conference Paper

Revising Typical Beliefs: One Revision to Rule Them All

• Jesse Heyninck
• Giovanni Casini
• Thomas Meyer
• Umberto Straccia

Propositional Typicality Logic (PTL) extends propositional logic with a connective • expressing the most typical (alias normal or conventional) situations in which a given sentence holds. As such, it generalises e. g. ~preferential logics that formalise reasoning with conditionals such as ``birds typically fly''. In this paper, we study revision of sets of PTL-sentences. We first show why it is necessary to extend the PTL-language with a possibility operator, and then define the revision of PTL-sentences syntactically and characterise it semantically. We show that this allows us to represent a wide variety of existing revision methods, such as propositional revision and revision of epistemic states. Furthermore, we provide several examples showing why our approach is innovative. In more detail, we study revision of a set of conditionals under preferential closure, and the addition and contraction of possible worlds from an epistemic state.

AIJ Journal 2023 Journal Article

Situated conditional reasoning

• Giovanni Casini
• Thomas Meyer
• Ivan Varzinczak

IJCAI Conference 2022 Conference Paper

Lexicographic Entailment, Syntax Splitting and the Drowning Problem

• Jesse Heyninck
• Gabriele Kern-Isberner
• Thomas Meyer

Lexicographic inference is a well-known and popular approach to reasoning with non-monotonic conditionals. It is a logic of very high-quality, as it extends rational closure and avoids the so-called drowning problem. It seems, however, this high quality comes at a cost, as reasoning on the basis of lexicographic inference is of high computational complexity. In this paper, we show that lexicographic inference satisfies syntax splitting, which means that we can restrict our attention to parts of the belief base that share atoms with a given query, thus seriously restricting the computational costs for many concrete queries. Furthermore, we make some observations on the relationship between c-representations and lexicographic inference, and reflect on the relation between syntax splitting and the drowning problem.

AAAI Conference 2021 Conference Paper

Contextual Conditional Reasoning

• Giovanni Casini
• Thomas Meyer
• Ivan Varzinczak

We extend the expressivity of classical conditional reasoning by introducing context as a new parameter. The enriched conditional logic generalises the defeasible conditional setting in the style of Kraus, Lehmann, and Magidor, and allows for a refined semantics that is able to distinguish, for example, between expectations and counterfactuals. In this paper we introduce the language for the enriched logic and define an appropriate semantic framework for it. We analyse which properties generally associated with conditional reasoning are still satisfied by the new semantic framework, provide a suitable representation result, and define an entailment relation based on Lehmann and Magidor’s generally-accepted notion of Rational Closure.

KR Conference 2020 Conference Paper

Rational Defeasible Belief Change

• Giovanni Casini
• Thomas Meyer
• Ivan Varzinczak

We present a formal framework for modelling belief change within a nonmonotonic reasoning system. Belief change and non-monotonic reasoning are two areas that are formally closely related, with recent attention being paid towards the analysis of belief change within a non-monotonic environment. In this paper we consider the classical AGM belief change operators, contraction and revision, applied to a defeasible setting in the style of Kraus, Lehmann, and Magidor. The investigation leads us to the consideration of the problem of iterated change, generalising the classical work of Darwiche and Pearl. We characterise a family of operators for iterated revision, followed by an analogous characterisation of operators for iterated contraction. We start considering belief change operators aimed at preserving logical consistency, and then characterise analogous operators aimed at the preservation of coherence—an important notion within the field of logic-based ontologies.

AIJ Journal 2019 Journal Article

On rational entailment for Propositional Typicality Logic

• Richard Booth
• Giovanni Casini
• Thomas Meyer
• Ivan Varzinczak

IJCAI Conference 2019 Conference Paper

Simple Conditionals with Constrained Right Weakening

• Giovanni Casini
• Thomas Meyer
• Ivan Varzinczak

In this paper we introduce and investigate a very basic semantics for conditionals that can be used to define a broad class of conditional reasoning. We show that it encompasses the most popular kinds of conditional reasoning developed in logic-based KR. It turns out that the semantics we propose is appropriate for a structural analysis of those conditionals that do not satisfy the property of Right Weakening. We show that it can be used for the further development of an analysis of the notion of relevance in conditional reasoning.

KR Conference 2018 Conference Paper

A Semantic Perspective on Belief Change in a Preferential Non-Monotonic Framework

• Giovanni Casini
• Thomas Meyer
• Eduardo Fermé
• Ivan Varzinczak

Belief change and non-monotonic reasoning are usually viewed as two sides of the same coin, with results showing that one can formally be defined in terms of the other. In this paper we investigate the integration of the two formalisms by studying belief change for a (preferential) non-monotonic framework. We show that the standard AGM approach to belief change can be transferred to a preferential non-monotonic framework in the sense that change operations can be defined on conditional knowledge bases. We take as a point of departure the results presented by Casini and Meyer (2017), and we develop and extend such results with characterisations based on semantics and entrenchment relations, showing how some of the constructions defined for propositional logic can be lifted to our preferential non-monotonic framework.

IJCAI Conference 2017 Conference Paper

Belief Change in a Preferential Non-monotonic Framework

• Giovanni Casini
• Thomas Meyer

Belief change and non-monotonic reasoning are usually viewed as two sides of the same coin, with results showing that one can formally be defined in terms of the other. In this paper we show that it also makes sense to analyse belief change within a (preferential) non-monotonic framework. We consider belief change operators in a non-monotonic propositional setting with a view towards preserving consistency. We show that the results obtained can also be applied to the preservation of coherence— an important notion within the field of logic-based ontologies. We adopt the AGM approach to belief change and show that standard AGM can be adapted to a preferential non-monotonic framework, with the definition of expansion, contraction, and revision operators, and corresponding representation results.

KR Conference 2016 Short Paper

Using Defeasible Information to Obtain Coherence

• Giovanni Casini
• Thomas Meyer

We consider the problem of obtaining coherence in a propositional knowledge base using techniques from Belief Change. Our motivation comes from the field of formal ontologies where coherence is interpreted to mean that a concept name has to be satisfiable. In the propositional case we consider here, this translates to a propositional formula being satisfiable. We define belief change operators in a framework of nonmonotonic preferential reasoning. We show how the introduction of defeasible information using contraction operators can be an effective means for obtaining coherence.

AIJ Journal 2010 Journal Article

Double preference relations for generalised belief change

• Richard Booth
• Samir Chopra
• Thomas Meyer
• Aditya Ghose

IJCAI Conference 2009 Conference Paper

• Richard Booth
• Thomas Meyer
• Ivan José Varzinczak

Standard belief contraction assumes an underlying logic containing full classical propositional logic, but there are good reasons for considering contraction in less expressive logics. In this paper we focus on Horn logic. In addition to being of interest in its own right, our choice is motivated by the use of Horn logic in several areas, including ontology reasoning in description logics. We consider three versions of contraction: entailment-based and inconsistency-based contraction (e-contraction and i-contraction, resp.), introduced by Delgrande for Horn logic, and package contraction (p-contraction), studied by Fuhrmann and Hansson for the classical case. We show that the standard basic form of contraction, partial meet, is too strong in the Horn case. We define more appropriate notions of basic contraction for all three types above, and provide associated representation results in terms of postulates. Our results stand in contrast to Delgrande’s conjectures that orderly maxichoice is the appropriate contraction for both e- and i-contraction. Our interest in p-contraction stems from its relationship with an important reasoning task in ontological reasoning: repairing the subsumption hierarchy in EL. This is closely related to p-contraction with sets of basic Horn clauses (Horn clauses of the form p → q). We show that this restricted version of p-contraction can also be represented as i-contraction.

KR Conference 2008 Conference Paper

Equilibria in Social Belief Removal

• Richard Booth
• Thomas Meyer

In studies of multi-agent interaction, especially in game theory, the notion of equilibrium often plays a prominent role. A typical scenario for the belief merging problem is one in which several agents pool their beliefs together to form a consistent "group" picture of the world. The aim of this paper is to define and study new notions of equilibria in belief merging. To do so, we assume the agents arrive at consistency via the use of a social belief removal function, in which each agent, using his own individual removal function, removes some belief from his stock of beliefs. We examine several notions of equilibria in this setting, assuming a general framework for individual belief removal due to Booth et al. We look at their inter-relations as well as prove their exitstance or otherwise. We also show how our equilibria can be seen as a generalisation of the idea of taking maximal consistent subsets of agents.

KR Conference 2008 Conference Paper

Semantic Preferential Subsumption

• Katarina Britz
• Johannes Heidema
• Thomas Meyer

We present a general preferential semantic framework for plausible subsumption in description logics, analogous to the KLM preferential semantics for propositional entailment. We introduce the notion of ordered interpretations for description logics, and use it to define two mutually dual non-deductive subsumption relations. We outline their properties and explain how they may be used for inductive and abductive reasoning respectively. We show that the preferential semantics for subsumption can be reduced to standard semantics of a sufficiently expressive description logic. This has the advantage that standard DL algorithms can be extended to reason about our notions of plausible subsumption.

KR Conference 2006 Conference Paper

A Bad Day Surfing is Better than a Good Day Working: How to Revise a Total Preorder

• Richard Booth
• Thomas Meyer
• Ka-Shu Wong

Most approaches to iterated belief revision are accompanied by some motivation for the use of the proposed revision operator (or family of operators), and typically encode enough information for uniquely determining one-step revision. But in those approaches describing a family of operators, there is usually little indication of how to proceed uniquely after the first revision step. In this paper we take a step towards addressing that deficiency by providing a formal framework which goes beyond the first revision step. The framework is obtained by enriching the preference information starting from the following intuitive idea: we associate to each world x two abstract objects x+ and x-, with the intuition that x+ represents x "on a good day", while x- represents x "on a bad day", and we assume that, in addition to preferences over the set of worlds, we are given preferences over this set of objects as well. The latter can be considered as meta-information which enables us to go beyond the first revision step of the revision operator being applied.

AAAI Conference 2006 Conference Paper

Finding Maximally Satisfiable Terminologies for the Description Logic ALC

• Thomas Meyer
• Richard Booth

For ontologies represented as Description Logic Tboxes, optimised DL reasoners are able to detect logical errors, but there is comparatively limited support for resolving such problems. One possible remedy is to weaken the available information to the extent that the errors disappear, but to limit the weakening process as much as possible. The most obvious way to do so is to remove just enough Tbox sentences to eliminate the errors. In this paper we propose a tableaulike procedure for finding maximally concept-satisfiable terminologies represented in the description logic ALC. We discuss some optimisation techniques, and report on preliminary, but encouraging, experimental results.

AAMAS Conference 2006 Conference Paper

Mutual Enrichment Through Nested Belief Change

• Laurent Perrussel
• Jean-Marc Thevenin
• Thomas Meyer

AAAI Conference 2005 Conference Paper

Knowledge Integration for Description Logics

• Thomas Meyer

Description logic reasoners are able to detect incoherences (such as logical inconsistency and concept unsatisfiability) in knowledge bases, but provide little support for resolving them. We propose to recast techniques for propositional inconsistency management into the description logic setting. We show that the additional structure afforded by description logic statements can be used to refine these techniques. Our focus in this paper is on the formal semantics for such techniques, although we do provide high-level decision procedures for the knowledge integration strategies discussed.

AAAI Conference 2004 Conference Paper

Logical Foundations of Negotiation: Outcome, Concession, and Adaptation

• Thomas Meyer
• Rex Kwok

This paper provides a logical framework for negotiation between agents that are assumed to be rational, cooperative and truthful. We present a characterisation of the permissible outcomes of a process of negotiation in terms of a set of rationality postulates, as well as a method for constructing exactly the rational outcomes. The framework is extended by describing two modes of negotiation from which an outcome can be reached. In the concessionary mode, agents are required to weaken their demands in order to accommodate the demands of others. In the adaptationist mode, agents are required to adapt to the demands of others in some appropriate fashion. Both concession and adaptation are characterised in terms of rationality postulates. We also provide methods for constructing exactly the rational concessions, as well as the rational adaptations. The central result of the paper is the observation that the outcomes obtained from the concessionary and adaptationist modes both correspond to the rational outcomes. We conclude by pointing out the links between negotiation and AGM belief change, and providing a glimpse of how this may be used to define a notion of preference-based negotiation.

KR Conference 2004 Conference Paper

Logical foundations of negotiation: strategies and preferences

• Norman Foo
• Rex Kwok
• Thomas Meyer
• Dongmo Zhang

This paper is a contribution towards the body of literature which views negotiation in a qualitative light. It builds on an existing logical framework for negotiation between rational, cooperative, truthful agents proposed by Meyer et al. We show that agents equipped with negotiation strategies corresponding to basic AGM belief revision operations are capable of reaching exactly the permissible deals defined and discussed in previous work. Each agent has to present a set of weakened demands to the other party who, in return, is obliged to accept all weakened demands. The acceptance of demands is modelled by basic AGM belief revision. We extend the logical framework of Meyer et al. by considering scenarios in which the initial demand sets of agents may vary. We show that it forces agents to limit their negotiation strategies to AGM belief revision satisfying the supplementary AGM postulates. This leads to the redefinition of a negotiation strategy as a reference relation on demands. This extended framework provides a description of the deals that an agent ought to consider as reasonable, but provides no information on how it should go about choosing a particular deal. We conclude with suggestions on how negotiation strategies can be used to do so.

AAAI Conference 2004 Conference Paper

Negotiation as Mutual Belief Revision

• Dongmo Zhang
• Thomas Meyer

This paper presents a logical framework for negotiation based on belief revision theory. We consider that a negotiation process is a course or multiple courses of mutual belief revision. A set of AGM-style postulates are proposed to capture the rationality of competitive and cooperative behaviors of negotiation. We first show that the AGM revision and its iterated extension is a special case of negotiation function. Then we show that a negotiation function can be constructed by two related iterated belief revision functions under a certain coordination mechanism. This provides a qualitative method for constructing negotiation space and rational concessions. It also shows a glimpse of how to express game-theoretical concepts in logical framework.