Kai Sauerwald

Juha Kontinen, Arne Meier, Kai Sauerwald

This paper establishes and proves representation theorems for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. Cumulative logics are famously given by System C. For propositional dependence logic, we show that System C entailments are exactly captured by cumulative models from Kraus, Lehmann and Magidor. On the other hand, we show that entailment in cumulative propositional logics with team semantics is exactly captured by cumulative and asymmetric models. For the latter, we also obtain equivalence with cumulative logics based on propositional logic with classical semantics. The proofs will be useful for proving representation theorems for other cumulative logics without negation and material implication.

Kai Sauerwald, Juha Kontinen, Arne Meier

This paper establishes and proves complexity results for entailment for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. As recently shown, cumulative logics are famously characterised by System~C and exactly captured by the cumulative models of Kraus, Lehmann and Magidor. This gives rise to the entailment problem via relational models, which is specifically considered here.

Lydia Blümel, Kai Sauerwald, Kenneth Skiba et al.

We show that deciding whether an argument a is stronger than an argument b with respect to the discussion-based semantics of Amgoud and Ben-Naim is decidable in polynomial time. At its core, this problem is about deciding whether, for two vertices in a graph, the number of walks of each length ending in those vertices is the same. We employ results from automata theory and reduce this problem to the equivalence problem for semiring automata. This offers a new perspective on the computational complexity of ranking semantics, an area in which the complexity of many semantics remains open.

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, a special kind of maxichoice operator. When AGM revision, respectively, AGM contraction, is realizable, linear change operators are a canonical realization.

Kai Sauerwald

We consider credibility-limited revision in the framework of belief change for epistemic spaces, permitting inconsistent belief sets and inconsistent beliefs. In this unrestricted setting, the class of credibility-limited revision operators does not include any AGM revision operators. We extend the class of credibility-limited revision operators in a way that all AGM revision operators are included while keeping the original spirit of credibility-limited revision. Extended credibility-limited revision operators are defined axiomatically. A semantic characterization of extended credibility-limited revision operators that employ total preorders on possible worlds is presented.

Christoph Beierle, Alexander Hahn, Diana Howey et al.

Forgetting as a knowledge management operation deliberately ignores parts of the knowledge and beliefs of an agent, for various reasons. Forgetting has many facets, one may want to forget parts of the syntax, a proposition, or a conditional. In the literature, two main operators suitable for performing forgetting have been proposed and investigated in depth: First, variable elimination is a syntactical method that blends out certain atomic variables to focus on the rest of the language. It has been mainly used in the area of logic programming and answer set programming. Second, contraction in AGM belief revision theory effectively removes propositions from belief sets under logical deduction. Both operations rely mainly on classical logics. In this article, we take an epistemic perspective and study forgetting operations in epistemic states with richer semantic structures, but with clear links to propositional logic. This allows us to investigate what forgetting in the epistemic background means, thereby lifting well-known and novel forgetting operations to the epistemic level. We present five general types of epistemic forgetting and instantiate them with seven concrete forgetting operations for Spohn's ranking functions. We take inspiration from postulates of forgetting both from logic programming and AGM theory to propose a rich landscape of axioms for evaluating forgetting operations. Finally, we evaluate all concrete forgetting operations according to all postulates, leading to a novel comprehensive overview highlighting differences and commonalities among the forgetting operators.

Kai Sauerwald, Kenneth Skiba, Eduardo Fermé et al.

We study how linear orders can be employed to realise choice functions for which the set of potential choices is restricted, i.e., the possible choice is not possible among the full powerset of all alternatives. In such restricted settings, constructing a choice function via a relation on the alternatives is not always possible. However, we show that one can always construct a choice function via a linear order on sets of alternatives, even when a fallback value is encoded as the minimal element in the linear order. The axiomatics of such choice functions are presented for the general case and the case of union-closed input restrictions. Restricted choice structures have applications in knowledge representation and reasoning, and here we discuss their applications for theory change and abstract argumentation.

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.

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.

Kai Sauerwald, Christoph Beierle

Iterated Belief Change is the research area that investigates principles for the dynamics of beliefs over (possibly unlimited) many subsequent belief changes. In this paper, we demonstrate how iterated belief change is connected to computation. In particular, we show that iterative belief revision is Turing complete, even under the condition that broadly accepted principles like the Darwiche-Pearl postulates for iterated revision hold.

Kai Sauerwald, Gabriele Kern-Isberner, Christoph Beierle

In this article, we consider iteration principles for contraction, with the goal of identifying properties for contractions that respect conditional beliefs. Therefore, we investigate and evaluate four groups of iteration principles for contraction which consider the dynamics of conditional beliefs. For all these principles, we provide semantic characterization theorems and provide formulations by postulates which highlight how the change of beliefs and of conditional beliefs is constrained, whenever that is possible. The first group is similar to the syntactic Darwiche-Pearl postulates. As a second group, we consider semantic postulates for iteration of contraction by Chopra, Ghose, Meyer and Wong, and by Konieczny and Pino Pérez, respectively, and we provide novel syntactic counterparts. Third, we propose a contraction analogue of the independence condition by Jin and Thielscher. For the fourth group, we consider natural and moderate contraction by Nayak. Methodically, we make use of conditionals for contractions, so-called contractionals and furthermore, we propose and employ the novel notion of $ α$-equivalence for formulating some of the new postulates.

Faiq Miftakhul Falakh, Sebastian Rudolph, Kai Sauerwald

We establish a generic, model-theoretic characterization of belief revision operators implementing the paradigm of minimal change according to the seminal work by Alchourrón, Gärdenfors, and Makinson (AGM). Our characterization applies to all Tarskian logics, that is, all logics with a classical model-theoretic semantics, and hence a wide variety of formalisms used in knowledge representation and beyond, including many for which a model-theoretic characterization has hitherto been lacking. Our starting point is the approach by Katsuno and Mendelzon (K&M), who provided such a characterization for propositional logic over finite signatures. We generalize K&M's approach to the setting of AGM-style revision over bases in arbitrary Tarskian logics, where base may refer to one of the various ways of representing an agent's beliefs (such as belief sets, arbitrary or finite sets of sentences, or single sentences). Our first core result is a representation theorem providing a two-way correspondence between AGM-style revision operators and specific assignments: functions associating every base to a "preference" relation over interpretations, which must be total but is - in contrast to prior approaches - not always transitive. As our second core contribution, we provide a characterization of all logics for which our result can be strengthened to assignments producing transitive preference relations (as in K&M's original work). Alongside these main contributions, we discuss diverse variants of our findings as well as ramifications for other areas of belief revision theory.

Marco Wilhelm, Diana Howey, Gabriele Kern-Isberner et al.

Activation-based conditional inference applies conditional reasoning to ACT-R, a cognitive architecture developed to formalize human reasoning. The idea of activation-based conditional inference is to determine a reasonable subset of a conditional belief base in order to draw inductive inferences in time. Central to activation-based conditional inference is the activation function which assigns to the conditionals in the belief base a degree of activation mainly based on the conditional's relevance for the current query and its usage history. Therewith, our approach integrates several aspects of human reasoning into expert systems such as focusing, forgetting, and remembering.

Kai Sauerwald, Gabriele Kern-Isberner, Christoph Beierle

The research on non-prioritized revision studies revision operators which do not accept all new beliefs. In this paper, we contribute to this line of research by introducing the concept of dynamic-limited revision, which are revisions expressible by a total preorder over a limited set of worlds. For a belief change operator, we consider the scope, which consists of those beliefs which yield success of revision. We show that for each set satisfying single sentence closure and disjunction completeness there exists a dynamic-limited revision having the union of this set with the beliefs set as scope. We investigate iteration postulates for belief and scope dynamics and characterise them for dynamic-limited revision. As an application, we employ dynamic-limited revision to studying belief revision in the context of so-called inherent beliefs, which are beliefs globally accepted by the agent. This leads to revision operators which we call inherence-limited. We present a representation theorem for inherence-limited revision, and we compare these operators and dynamic-limited revision with the closely related credible-limited revision operators.

Faiq Miftakhul Falakh, Sebastian Rudolph, Kai Sauerwald

The AGM postulates by Alchourrón, Gärdenfors, and Makinson continue to represent a cornerstone in research related to belief change. We generalize the approach of Katsuno and Mendelzon (KM) for characterizing AGM base revision from propositional logic to the setting of (multiple) base revision in arbitrary monotonic logics. Our core result is a representation theorem using the assignment of total - yet not transitive - "preference" relations to belief bases. We also provide a characterization of all logics for which our result can be strengthened to preorder assignments (as in KM's original work).

Kai Sauerwald, Jonas Haldimann, Martin von Berg et al.

Descriptor revision by Hansson is a framework for addressing the problem of belief change. In descriptor revision, different kinds of change processes are dealt with in a joint framework. Individual change requirements are qualified by specific success conditions expressed by a belief descriptor, and belief descriptors can be combined by logical connectives. This is in contrast to the currently dominating AGM paradigm shaped by Alchourrón, Gärdenfors, and Makinson, where different kinds of changes, like a revision or a contraction, are dealt with separately. In this article, we investigate the realisation of descriptor revision for a conditional logic while restricting descriptors to the conjunction of literal descriptors. We apply the principle of conditional preservation developed by Kern-Isberner to descriptor revision for conditionals, show how descriptor revision for conditionals under these restrictions can be characterised by a constraint satisfaction problem, and implement it using constraint logic programming. Since our conditional logic subsumes propositional logic, our approach also realises descriptor revision for propositional logic.

Kai Sauerwald, Gabriele Kern-Isberner, Christoph Beierle

According to Boutillier, Darwiche, 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. This is especially because for iterated belief change the connection between revision and contraction via the Levi and Harper identity is not straightforward, and therefore, characterisation results do not transfer easily between iterated revision and contraction. In this article, we develop an axiomatisation of iterated contraction in terms of changing conditional beliefs. We prove that the new set of postulates conforms semantically to the class of operators like the ones given by Konieczny and Pino Pérez for iterated contraction.

Kai Sauerwald, Christoph Beierle

While research on iterated revision is predominant in the field of iterated belief change, the class of iterated contraction operators received more attention in recent years. In this article, we examine a non-prioritized generalisation of iterated contraction. In particular, the class of weak decrement operators is introduced, which are operators that by multiple steps achieve the same as a contraction. Inspired by Darwiche and Pearl's work on iterated revision the subclass of decrement operators is defined. For both, decrement and weak decrement operators, postulates are presented and for each of them a representation theorem in the framework of total preorders is given. Furthermore, we present two sub-types of decrement operators.