Thomas Andreas Meyer

NMR Workshop 2025 Conference Paper

Semantic Bridges Between First Order c-Representations and Cost-Based Semantics: An Initial Perspective

• Nicholas Leisegang
• Giovanni Casini
• Thomas Andreas Meyer

Weighted-knowledge bases and cost-based semantics represent a recent formalism introduced by Bienvenu et al. for Ontology Mediated Data Querying in the case where a given knowledge base is inconsistent. This is done by adding a weight to each statement in the knowledge base (KB), and then giving each DL interpretation a cost based on how often it breaks rules in the KB. In this paper we compare this approach with 𝑐-representations, a form of non-monotonic reasoning originally introduced by Kern-Isberner. 𝑐-Representations describe a means to interpret defeasible concept inclusions of the form 𝐶 ⊏ ∼ 𝐷 (read “instances of 𝐶 are usually instances of 𝐷”) in the first-order case. This is done by assigning a numerical ranking to each interpretations via penalties for each violated conditional. We compare these two approaches on a semantic level. In particular, we show that under certain conditions a weighted knowledge base and a set of defeasible conditionals can generate the same ordering on interpretations, and therefore an equivalence of semantic structures up to relative cost. Moreover, we compare entailment described in both cases, where certain notions are equivalently expressible in both formalisms. Our results have the potential to benefit further work on both cost-based semantics and c-representations.

NMR Workshop 2025 Conference Paper

Toward Defeasible Reasoning Using Knowledge Compilation Techniques

• Luke Slater
• Thomas Andreas Meyer
• Jesse Heyninck

We explore the use of ordered binary decision diagrams (OBDDs) and multi-terminal binary decision diagrams (MTBDDs) for compiling and executing defeasible reasoning, focusing on System Z, also known as rational closure. We introduce an OBDD-based algorithm for System Z inference that parallels traditional SAT-based approaches. Additionally, we investigate the use of MTBDDs for encoding ordinal conditional functions (OCFs), providing a more general and unified knowledge compilation framework for defeasible reasoning tasks involving ranking functions. While our primary focus is on System Z, the proposed techniques are applicable to other forms of defeasible reasoning and conditional logic more broadly. Experimental results demonstrate that OBDDs can significantly accelerate inference. However, our evaluation is limited to synthetically generated belief bases, and further research is needed to validate benefits in real-world scenarios. Overall, our findings suggest that binary decision diagrams offer a promising alternative to SAT-based methods for defeasible reasoning, and warrant further investigation.

NMR Workshop 2024 Conference Paper

Ranking-based Defeasible Reasoning for Restricted First-Order Conditionals Applied to Description Logics

• Alexander Hahn 0001
• Gabriele Kern-Isberner
• Thomas Andreas Meyer

Nonmonotonic reasoning based on ordinal conditional functions (OCFs), often called ranking functions, and description logics are both well-established methodologies in knowledge representation and reasoning. However, nonmonotonic reasoning mainly focuses on propositional logic as a base logic, while description logics investigate fragments of first-order logic for efficient reasoning with terminological knowledge. In this paper, we investigate how OCFs can be employed to define inference relations induced from first-order conditional knowledge bases. The goal of this work is to present first steps towards an interpretation of defeasible subsumptions in description logics (DL) which is thoroughly based on conditionals and ranking functions. In the process, we adapt a recently proposed DL version of the KLM postulates, a popular framework for non-monotonic reasoning from propositional knowledge bases, for the use with conditional first-order logic. Moreover, we consider some additional recently proposed rationality postulates for a KLM approach based on (restricted) first-order logic. Concrete examples are provided for reasoning with strategic c-representations, a special type of ranking functions based on the underlying conditional structures of a knowledge base, yielding high-quality non-monotonic inferences without the need to specify external relations, e. g. , expressing typicality among individuals.

NMR Workshop 2024 Conference Paper

The Role of Syntax in Inductive Inference: A Property-based Study

• Jesse Heyninck
• Richard Booth 0001
• Thomas Andreas Meyer

The study of inference operators frequently involves the introduction of properties to which such operators should conform. Amongst other advantages, the property-based approach helps to restrict the range of operators, and to classify and categorise the type of inference being studied. This paper continues this tradition by proposing a number of properties for the class of inductive inference operators. We study the interaction of these properties, both with one another, and with other well-known properties for inductive inference. We also test a number of well-known inductive inference operators against the newly proposed, and some existing properties.

JELIA Conference 2023 Conference Paper

Rational Closure Extension in SPO-Representable Inductive Inference Operators

• Jonas Haldimann
• Thomas Andreas Meyer
• Gabriele Kern-Isberner
• Christoph Beierle

Abstract The class of inductive inference operators that extend rational closure, as introduced by Lehmann or via Pearl’s system Z, exhibits desirable inference characteristics. The property that formalizes this, known as (RC Extension), has recently been investigated for basic defeasible entailment relations. In this paper, we explore (RC Extension) for more general classes of inference relations. First, we semantically characterize (RC Extension) for preferential inference relations in general. Then we focus on operators that can be represented with strict partial orders (SPOs) on possible worlds and characterize SPO-representable inductive inference operators. Furthermore, we show that for SPO-representable inference operators, (RC Extension) is semantically characterized as a refinement of the Z-rank relation on possible worlds.

NMR Workshop 2022 Conference Paper

Asking Human Reasoners to Judge Postulates of Belief Change for Plausibility

• Clayton K. Baker
• Thomas Andreas Meyer

Empirical methods have been used to test whether human reasoning conforms to models of reasoning in logic-based artificial intelligence. This work investigates through surveys whether postulates of belief revision and update are plausible with human reasoners. The results show that participants’ reasoning tend to be consistent with the postulates of belief revision and belief update when judging the premises and conclusion of the postulate separately.

NMR Workshop 2022 Conference Paper

Conditional Syntax Splitting, Lexicographic Entailment and the Drowning Effect

• Jesse Heyninck
• Gabriele Kern-Isberner
• Thomas Andreas Meyer

Lexicographic inference [1] is a well-behaved and popular approach to reasoning with non-monotonic conditionals. In recent work we have shown that lexicographic inference satisfies syntax splitting, which means we can restrict our attention to parts of the belief base that share atoms with a given query. 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 satisfies conditional syntax splitting, and connect conditional syntax splitting to several known properties from the literature on non-monotonic reasoning, including the drowning effect.

NMR Workshop 2022 Conference Paper

Situated Conditionals - A Brief Introduction

• Giovanni Casini
• Thomas Andreas Meyer
• Ivan Varzinczak

We extend the expressivity of classical conditional reasoning by introducing situation 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. 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.

JELIA Conference 2019 Conference Paper

A Bayesian Extension of the Description Logic ALC

• Leonard Botha
• Thomas Andreas Meyer
• Rafael Peñaloza

Abstract Description logics (DLs) are well-known knowledge representation formalisms focused on the representation of terminological knowledge. A probabilistic extension of a light-weight DL was recently proposed for dealing with certain knowledge occurring in uncertain contexts. In this paper, we continue that line of research by introducing the Bayesian extension \(\mathcal {BALC}\) of the DL \(\mathcal {ALC}\). We present a tableau-based procedure for deciding consistency, and adapt it to solve other probabilistic, contextual, and general inferences in this logic. We also show that all these problems remain ExpTime -complete, the same as reasoning in the underlying classical \(\mathcal {ALC}\).

JELIA Conference 2019 Conference Paper

Taking Defeasible Entailment Beyond Rational Closure

• Giovanni Casini
• Thomas Andreas Meyer
• Ivan Varzinczak

Abstract We present a systematic approach for extending the KLM framework for defeasible entailment. We first present a class of basic defeasible entailment relations, characterise it in three distinct ways and provide a high-level algorithm for computing it. This framework is then refined, with the refined version being characterised in a similar manner. We show that the two well-known forms of defeasible entailment, rational closure and lexicographic closure, fall within our refined framework, that rational closure is the most conservative of the defeasible entailment relations within the framework (with respect to subset inclusion), but that there are forms of defeasible entailment within our framework that are more “adventurous” than lexicographic closure.

ECAI Conference 2016 Conference Paper

On Revision of Partially Specified Convex Probabilistic Belief Bases

• Gavin Rens
• Thomas Andreas Meyer
• Giovanni Casini

We propose a method for an agent to revise its incomplete probabilistic beliefs when a new piece of propositional information is observed. In this work, an agent's beliefs are represented by a set of probabilistic formulae - a belief base. The method involves determining a representative set of 'boundary' probability distributions consistent with the current belief base, revising each of these probability distributions and then translating the revised information into a new belief base. We use a version of Lewis Imaging as the revision operation. The correctness of the approach is proved. An analysis of the approach is done against six rationality postulates. The expressivity of the belief bases under consideration are rather restricted, but has some applications. We also discuss methods of belief base revision employing the notion of optimum entropy, and point out some of the benefits and difficulties in those methods. Both the boundary distribution method and the optimum entropy methods are reasonable, yet yield different results.

IJCAI Conference 2015 Conference Paper

On the Entailment Problem for a Logic of Typicality

• Richard Booth
• Giovanni Casini
• Thomas Andreas Meyer
• Ivan Jos
• eacute; Varzinczak

Propositional Typicality Logic (PTL) is a recently proposed logic, obtained by enriching classical propositional logic with a typicality operator. In spite of the non-monotonic features introduced by the semantics adopted for the typicality operator, the obvious Tarskian definition of entailment for PTL remains monotonic and is therefore not appropriate. We investigate different (semantic) versions of entailment for PTL, based on the notion of Rational Closure as defined by Lehmann and Magidor for KLM-style conditionals, and constructed using minimality. Our first important result is an impossibility theorem showing that a set of proposed postulates that at first all seem appropriate for a notion of entailment with regard to typicality cannot be satisfied simultaneously. Closer inspection reveals that this result is best interpreted as an argument for advocating the development of more than one type of PTL entailment. In the spirit of this interpretation, we define two primary forms of entailment for PTL and discuss their advantages and disadvantages.

JELIA Conference 2014 Conference Paper

Relevant Closure: A New Form of Defeasible Reasoning for Description Logics

• Giovanni Casini
• Thomas Andreas Meyer
• Kodylan Moodley
• Riku Nortje

Abstract Among the various proposals for defeasible reasoning for description logics, Rational Closure, a procedure originally defined for propositional logic, turns out to have a number of desirable properties. Not only it is computationally feasible, but it can also be implemented using existing classical reasoners. One of its drawbacks is that it can be seen as too weak from the inferential point of view. To overcome this limitation we introduce in this paper two extensions of Rational Closure: Basic Relevant Closure and Minimal Relevant Closure. As the names suggest, both rely on defining a version of relevance. Our formalisation of relevance in this context is based on the notion of a justification (a minimal subset of sentences implying a given sentence). This is, to our knowledge, the first proposal for defining defeasibility in terms of justifications—a notion that is well-established in the area of ontology debugging. Both Basic and Minimal Relevant Closure increase the inferential power of Rational Closure, giving back intuitive conclusions that cannot be obtained from Rational Closure. We analyse the properties and present algorithms for both Basic and Minimal Relevant Closure, and provide experimental results for both Basic Relevant Closure and Minimal Relevant Closure, comparing it with Rational Closure.

LPAR Conference 2013 Conference Paper

Prediction and Explanation over DL-Lite Data Streams

• Szymon Klarman
• Thomas Andreas Meyer

Abstract Stream reasoning is an emerging research area focusing on the development of reasoning techniques applicable to streams of rapidly changing, semantically enhanced data. In this paper, we consider data represented in Description Logics from the popular DL- Lite family, and study the logic foundations of prediction and explanation over DL- Lite data streams, i. e. , reasoning from finite segments of streaming data to conjectures about the content of the streams in the future or in the past. We propose a novel formalization of the problem based on temporal “past-future” rules, grounded in Temporal Query Language. Such rules can naturally accommodate complex data association patterns, which are typically discovered through data mining processes, with logical and temporal constraints of varying expressiveness. Further, we analyse the computational complexity of reasoning with rules expressed in different fragments of the temporal language. As a result, we draw precise demarcation lines between NP-, DP- and PSpace -complete variants of our setting and, consequently, suggest relevant restrictions rendering prediction and explanation more feasible in practice.

LPAR Conference 2013 Conference Paper

Reachability Modules for the Description Logic $\mathcal{SRIQ}$

• Riku Nortje
• Katarina Britz
• Thomas Andreas Meyer

Abstract In this paper we investigate module extraction for the Description Logic \(\mathcal{SRIQ}\). We formulate modules in terms of the reachability problem for directed hypergraphs. Using inseparability relations, we investigate the module-theoretic properties of reachability modules and show by means of an empirical evaluation that these modules have the potential of being substantially smaller than syntactic locality modules.

JELIA Conference 2012 Conference Paper

PTL: A Propositional Typicality Logic

• Richard Booth 0001
• Thomas Andreas Meyer
• Ivan Varzinczak

Abstract We introduce Propositional Typicality Logic (PTL), a logic for reasoning about typicality. We do so by enriching classical propositional logic with a typicality operator of which the intuition is to capture the most typical (or normal) situations in which a formula holds. The semantics is in terms of ranked models as studied in KLM-style preferential reasoning. This allows us to show that rational consequence relations can be embedded in our logic. Moreover we show that we can define consequence relations on the language of PTL itself, thereby moving beyond the propositional setting. Building on the existing link between propositional rational consequence and belief revision, we show that the same correspondence holds for rational consequence and belief revision on PTL. We investigate entailment for PTL, and propose two appropriate notions thereof.

ECAI Conference 2010 Conference Paper

Horn Belief Change: A Contraction Core

• Richard Booth 0001
• Thomas Andreas Meyer
• Ivan Varzinczak
• Renata Wassermann

We show that Booth et al. 's Horn contraction based on infra-remainder sets corresponds exactly to kernel contraction for belief sets. This result is obtained via a detour through Horn contraction for belief bases, which supports the conjecture that Horn belief change is best viewed as a "hybrid" version of belief set change and belief base change. Moreover, the link with base contraction gives us a more elegant representation result for Horn contraction for belief sets in which a version of the Core-retainment postulate features.

LORI Conference 2009 Conference Paper

A General Family of Preferential Belief Removal Operators

• Richard Booth 0001
• Thomas Andreas Meyer
• Chattrakul Sombattheera

Abstract Most belief change operators in the AGM tradition assume an underlying plausibility ordering over the possible worlds which is transitive and complete. A unifying structure for these operators, based on supplementing the plausibility ordering with a second, guiding, relation over the worlds was presented in [5]. However it is not always reasonable to assume completeness of the underlying ordering. In this paper we generalise the structure of [5] to allow incomparabilities between worlds. We axiomatise the resulting class of belief removal functions, and show that it includes an important family of removal functions based on finite prioritised belief bases.

ECAI Conference 2006 Conference Paper

Mutual Enrichment for Agents Through Nested Belief Change: A Semantic Approach

• Laurent Perrussel
• Jean-Marc Thévenin
• Thomas Andreas Meyer

ECAI Conference 2004 Conference Paper

A Unifying Semantics for Belief Change

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

NMR Workshop 2004 Conference Paper

A unifying semantics for belief change

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

Many belief change formalisms employ plausibility orderings over the set of possible worlds to determine how the beliefs of an agent ought to be modified after the receipt of a new epistemic input. While most such possible world semantics rely on a single ordering, we look at using an extra ordering to aid in guiding the process of belief change. We show that this provides a unifying semantics for a wide variety of belief change operators. By varying the conditions placed on the second ordering, different families of known belief change operators can be captured, including AGM belief contraction and revision (Alchourrón, Gärdenfors, & Makinson 1985), severe withdrawal (Rott & Pagnucco 1999), systematic withdrawal (Meyer et al. 2002), and the linear liberation and σ-liberation operators of (Booth et al. 2003). Our approach also identifies novel classes of belief change operators that are worth further investigation.

TARK Conference 2003 Conference Paper

Belief liberation (and retraction)

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

We provide a formal study of belief retraction operators that do not necessarily satisfy the (Inclusion) postulate. Our intuition is that a rational description of belief change must do justice to cases in which dropping a belief can lead to the inclusion, or 'liberation', of others in an agent's corpus. We provide a few possible weakenings of the (Inclusion) postulate and then provide two models of liberation via retraction operators, a-liberation and linear liberation. We show that the class of c-liberation operators is included in the class of linear ones and provide axiomatic characterisations for each class. We also show how any given retraction operator (including the liberation operators) can be 'converted' into either a withdrawal operator (i. e. , -satisfying (Inclusion)) or a revision operator via (a slight v~iant of) the Harper Identity and the Levi Identity respectively.

NMR Workshop 2002 Conference Paper

Iterated revision and the axiom of recovery: a unified treatment via epistemic states

• Samir Chopra
• Aditya Ghose
• Thomas Andreas Meyer

The axiom of recovery, while capturing a central intuition regarding belief change, has been the source of much controversy. We argue briefly against putative counterexamples to the axiom— while agreeing that some of their insight deserves to be preserved—and present additional recovery-like axioms in a framework that uses epistemic states, which encode preferences, as the object of revisions. This provides a framework in which iterated revision becomes possible and makes explicit the connection between iterated belief change and the axiom of recovery. We provide a representation theorem that connects the semantic conditions that we impose on iterated revision and the additional syntactical properties mentioned. We also show some interesting similarities between our framework and that of Darwiche-Pearl [4]. In particular, we show that the intuitions underlying the controversial (C2) postulate are captured by the recovery axiom and our recovery-like postulates (the latter can be seen as weakenings of (C2).

ECAI Conference 2002 Conference Paper

Iterated revision and the axiom of recovery: A unified treatment via epistemic states

• Samir Chopra
• Aditya Ghose
• Thomas Andreas Meyer

NMR Workshop 2002 Conference Paper

Some logics of belief and disbelief

• Samir Chopra
• Johannes Heidema
• Thomas Andreas Meyer

The introduction of explicit notions of rejection, or disbelief, into logics for knowledge representation can be justified in a number of ways. Motivations range from the need for versions of negation weaker than classical negation, to the explicit recording of classic belief contraction operations in the area of belief change, and the additional levels of expressivity obtained from an extended version of belief change which includes disbelief contraction. In this paper we present four logics of disbelief which address some or all of these intuitions. Soundness and completeness results are supplied and the logics are compared with respect to applicability and utility.