Author name cluster

Kai Sauerwald

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

2 author rows

KR Conference 2025 Conference Paper

A Framework for Inconsistency-tolerant Reasoning with Sets of Models

Yehia Hatab
Kai Sauerwald
Matthias Thimm

We propose a framework for reasoning from inconsistent knowledge bases using minimal hitting sets, i. e. , sets of interpretations such that each formula of the knowledge base is satisfied by at least one those interpretations. By additionally considering preference orders over minimal hitting sets, we can define a wide variety of non-monotonic inference relations. We consider concrete preference orders based on set inclusion, cardinality, the number of conflicting atoms within the hitting set, and using the Hamming distance between pairs of interpretations. We compare the resulting inference relations, characterize their logical properties, and position them relative to classical inference from maximal consistent subsets. Finally, we show that inference based on minimal conflicting atoms coincides with reasoning in Priest’s 3-valued logic.

PDF Details DOI

KR Conference 2025 Conference Paper

On the Complexity and Properties of Preferential Propositional Dependence Logic

Kai Sauerwald
Arne Meier
Juha Kontinen

This paper considers the complexity and properties of KLM-style preferential reasoning in the setting of propositional logic with team semantics and dependence atoms, also known as propositional dependence logic. Preferential team-based reasoning is shown to be cumulative, yet violates System P. We give intuitive conditions that fully characterise those cases where preferential propositional dependence logic satisfies System P. We show that these characterisations do, surprisingly, not carry over to preferential team-based propositional logic. Furthermore, we show how classical entailment and dependence logic entailment can be expressed in terms of non-trivial preferential models. Finally, we present the complexity of preferential team-based reasoning for two natural representations. This includes novel complexity results for classical (non-team-based) preferential reasoning.

PDF Details DOI

NMR Workshop 2025 Conference Paper

The KLM Representation Theorem for System C, Formally

Jonathan Walther
Kai Sauerwald
Jesse Heyninck

We present a formalization of the proof of the correspondence between cumulative non-monotonic reasoning and System C in a proof assistant. Reasoning based on System C is the cornerstone of non-monotonic reasoning and was given a semantics via cumulative models by Kraus, Lehmann and Magidor. Our proof is inspired by the original proof and written in the proof system Rocq and focuses on propositional logic. Due to the features of Rocq, the proof implicitly yields a verified implementation of System C reasoning.

Details

NMR Workshop 2024 Conference Paper

A First Peek into Preferential Logics with Team Semantics

Kai Sauerwald
Juha Kontinen

This paper considers KLM-style preferential non-monotonic reasoning in the setting of propositional team semantics. We show that team-based propositional logics naturally give rise to cumulative non-monotonic entailment relations. Motivated by the non-classical interpretation of disjunction in team semantics, we give a precise characterization for preferential models for propositional dependence logic satisfying all of System P postulates. Furthermore, we show how classical entailment and dependence logic entailment can be expressed in terms of non-trivial preferential models.

Details

NMR Workshop 2024 Conference Paper

A Hitting Set Approach to Inconsistent-Tolerant Reasoning

Yehia Hatab
Kai Sauerwald
Matthias Thimm

This paper introduces four novel inconsistency-tolerant inference relations for knowledge bases. These relations are based on the minimal hitting sets of a knowledge base, which are sets of interpretations that contains a model of every formula in the knowledge base. We prove several useful properties of hitting sets and the inference relations based on them. The full landscape of the relationships between the four novel inference relations and the two inferences based on maximal consistent subsets by Rescher and Manor is given. We show that all of the considered inference relations are non-monotonic and satisfy several System P properties. Finally, we show that the respective complexity of inference is at most in the second level of the polynomial hierarchy.

Details

KR Conference 2024 Conference Paper

The Realizability of Revision and Contraction Operators in Epistemic Spaces

Kai Sauerwald
Matthias Thimm

This paper studies the realizability of belief revision and belief contraction operators in epistemic spaces. We observe that AGM revision and AGM contraction operators for epistemic spaces are only realizable in precisely determined epistemic spaces. We define the class of linear change operators, which are a special kind of maxichoice operators. When AGM revision, respectively, AGM contraction, is realizable, linear change operators are a canonical realization.

PDF Details DOI

FLAP Journal 2023 Journal Article

Activation-based Conditional Inference.

Marco Wilhelm
Diana Howey
Gabriele Kern-Isberner
Kai Sauerwald
Christoph Beierle

Activation-based conditional inference (ActInf) combines conditional rea- soning and ACT-R, a cognitive architecture developed to formalize human rea- soning, and therewith provides a powerful inference formalism which makes it possible to integrate several aspects of human reasoning, such as focusing, forgetting, and remembering, into formal uncertain reasoning. The basic idea of activation-based conditional inference is to determine a reasonable, cogni- tively adequate subset of a conditional belief base before drawing inductive inferences. Central to activation-based conditional inference is the activation function which assigns to the conditionals in the belief base a degree of acti- vation mainly based on the conditional’s relevance for the current query and its usage history. Here, we develop a blueprint for activation-based conditional inference and illustrate how focusing, forgetting, and remembering are included within our framework.

PDF Details

KR Conference 2022 Conference Paper

Iterated Belief Change, Computationally

Kai Sauerwald
Christoph Beierle

This paper considers belief change in the Darwiche-Pearl framework. We demonstrate that iterative belief revision is Turing complete by showing how revision operators over ranking functions can simulate every Turing machine. Our result holds even under the condition that the broadly accepted Darwiche-Pearl postulates for iterated revision hold.

PDF Details DOI

JELIA Conference 2021 Conference Paper

Conditional Descriptor Revision and Its Modelling by a CSP

Jonas Haldimann
Kai Sauerwald
Martin von Berg
Gabriele Kern-Isberner
Christoph Beierle

Abstract Descriptor revision is a belief change framework that was introduced by Hansson as an alternative to the currently prevailing AGM paradigm. One central idea of descriptor revision is to describe the desired outcome of a belief change. Thus, descriptor revision allows expressing different kinds of belief change operations like revision or contraction in a structured and combined way. In this paper, we investigate the framework of conditional descriptor revision. Conditional descriptor revision is a variation of descriptor revision aimed at the revision of ranking functions in the context of conditional logic. It is obtained by applying descriptor revision to conditional logic and additionally requiring the belief changes to fulfil the principle of conditional preservation. We show how conditional descriptor revision can be characterized by a constraint satisfaction problem (CSP). In contrast to previous work, we cover the full descriptor language over conditionals closed under conjunction, disjunction, and negation. We also line out an implementation of conditional descriptor revision based on its CSP representation. Since propositional logic can be embedded into conditional logic, our approach also provides descriptor revision for propositional logic.

Details

ECAI Conference 2020 Conference Paper

A Conditional Perspective for Iterated Belief Contraction

Kai Sauerwald
Gabriele Kern-Isberner
Christoph Beierle

According to Boutillier, Darwiche and Pearl and others, principles for iterated revision can be characterised in terms of changing beliefs about conditionals. For iterated contraction, a similar formulation is not known. In particular, the characterisation for revision does not immediately yield a characterisation for contraction, because in the setting of iterated belief change, revision and contraction are not easily interdefinable. In this article, we develop two axiomatisations of iterated contraction, the first one in terms of changing conditional beliefs, and the second one by employing a new notion of equivalence. We prove that each of these new sets of postulates conforms semantically to the class of operators like the ones given by Konieczny and Pino Pérez for iterated contraction.

Details

ECAI Conference 2020 Conference Paper

Cognitive Logics - Features, Formalisms, and Challenges

Marco Ragni
Gabriele Kern-Isberner
Christoph Beierle
Kai Sauerwald

Logic is responsible for scientific progress in many disciplines. In particular, computer science and AI would be impossible without it. Classical logics have long been accepted as a normative framework for human reasoning to capture correct reasoning. However, many psychological findings such as the Wason Selection Task have demonstrated that classical logic cannot serve as a possible descriptive language for the human inference process, which is the aim of what we call a cognitive logic. Recently, some nonmonotonic logics have been employed to explain human inferences for some well-known examples. In this paper, we discuss possible features of cognitive logics, present first results, and highlight new challenges.

Details