Non-monotonic reasoning is essential for drawing plausible conclusions from incomplete information. Many approaches model changing belief states using Ordinal Conditional Functions (OCFs), which assign degrees of surprise to possible worlds. This paper demonstrates how OCFs are ideally suited for the knowledge compilation paradigm, particularly with Binary Decision Diagrams (BDDs). We introduce a compilation pipeline for System Z, a prominent ranking-based semantics, which pre-compiles a conditional knowledge base into a set of materialized theories represented by BDDs. This compilation enables polynomial-time conditional entailment and efficient, incremental updates, avoiding costly re-computation. We further extend this approach using Algebraic Decision Diagrams (ADDs) to directly compile the entire ranking function, facilitating direct and efficient implementation of complex belief revision operations such as Spohn conditioning.

In this paper, we present a general framework for ranking sets of arguments in abstract argumentation frameworks based on their plausibility of acceptance. We present a generalisation of Dung’s extension semantics as extension-ranking semantics, which induce a preorder over the power set of all arguments, allowing us to state that one set is “closer” to being acceptable than another. To evaluate the extension-ranking semantics, we introduce a number of principles that a well-behaved extensionranking semantics should satisfy. We consider several simple base relations, each of which models a single central aspect of argumentative reasoning. The combination of these base relations provides us with a family of extension-ranking semantics.

Conditional independence is a crucial concept supporting adequate modelling and efficient reasoning in probabilistics. In knowledge representation, the idea of conditional independence has also been introduced for specific formalisms, such as propositional logic and belief revision. In this paper, the notion of conditional independence is studied in the algebraic framework of approximation fixpoint theory. This gives a language-independent account of conditional independence that can be straightforwardly applied to any logic with fixpoint semantics. It is shown how this notion allows to reduce global reasoning to parallel instances of local reasoning, leading to fixed-parameter tractability results. Furthermore, relations to existing notions of conditional independence are discussed and the framework is applied to normal logic programming.

Approximation fixpoint theory (AFT) is a robust and popular mathematical framework that characterizes many nonmonotonic semantics, where the construction of stable fixpoints, called stable revision, play a central role. Nondeterministic AFT is a recent development that redefines AFT for a nondeterministic setting to capture disjunctive semantics. This theory departs from traditional AFT by introducing distinct definitions, thus raising the question of whether deterministic AFT can be adopted directly to define nondeterministic stable revision. This work proposes such an alternate theory and creates a new way to study disjunctive semantics in terms of normal (non-disjunctive) knowledge bases. To demonstrate the viability of our framework, we show how to capture stable and partial stable models for disjunctive logic programs. We then study the relationships between this alternative theory and the state-of-the-art nondeterministic AFT.

Fuzzy logic programming is an established approach for reasoning under uncertainty. Several semantics from classical, two-valued logic programming have been generalized to the case of fuzzy logic programs. In this paper, we show that two of the most prominent classical semantics, namely the stable model and the well-founded semantics, can be reconstructed within the general framework of approximation fixpoint theory (AFT). This not only widens the scope of AFT from two- to many-valued logics, but allows a wide range of existing AFT results to be applied to fuzzy logic programming. As first examples of such applications, we clarify the formal relationship between existing semantics, generalize the notion of stratification from classical to fuzzy logic programs, and devise “more precise” variants of the semantics.

Constraint Logic Programming (CLP) is a logic programming formalism used to solve problems requiring the consideration of constraints, like resource allocation and automated planning and scheduling. It has previously been extended in various directions, for example to support fuzzy constraint satisfaction, uncertainty, or negation, with different notions of semiring being used as a unifying abstraction for these generalisations. None of these extensions have studied clauses with negation allowed in the body. We investigate an extension of CLP which unifies many of these extensions and allows negation in the body. We provide semantics for such programs, using the framework of approximation fixpoint theory, and give a detailed overview of the impacts of properties of the semirings on the resulting semantics. As such, we provide a unifying framework that captures existing approaches and allows to extend them with a more expressive language.

Splitting techniques in knowledge representation help focus on relevant parts of a belief base and reduce the complexity of reasoning generally. In this paper, we propose a generalization of safe conditional syntax splittings that broadens the applicability of splitting postulates for inductive inference from belief bases. In contrast to safe conditional syntax splitting, our generalized notion supports syntax splittings of a belief base ∆ where the subbases of ∆ may share atoms and nontrivial conditionals. We illustrate how this new notion overcomes limitations of previous splitting concepts, and we identify genuine splittings, separating them from simple splittings that do not provide benefits for inductive inference from ∆. We introduce adjusted inference postulates based on our generalization of conditional syntax splitting. We evaluate several inductive inference operators with respect to these postulates, and show that generalized safe conditional syntax splitting is a strictly stronger requirement for inductive inference operators, covering more syntax splitting applications.

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.

Abstract This paper continues an established line of research about the relations between argumentation theory, particularly assumption-based argumentation, and different kinds of logic programs. In particular, we extend known result of Bondarenko, Dung, Kowalski and Toni, and of Caminada and Schulz, by showing that assumption-based argumentation can represent not only normal logic programs, but also disjunctive logic programs under the stable model semantics. For this, we consider some inference rules for disjunction that the core logic of the argumentation frameworks should respect, and show the correspondence to the handling of disjunctions in the heads of the logic programs’ rules.

The concept of conditional syntax splitting for inductive inference from conditional belief bases has been proposed as a generalization of syntax splitting which also covers cases where the conditionals in the subbases share some atoms. p-Entailment and system Z fail to satisfy conditional syntax splitting, and up to now, only two inductive inference operators, lexicographic inference and system W, have been shown to satisfy this property. In this paper, we introduce the concept of conditional semantic splitting. We show that c-representations satisfy a core postulate relating conditional splittings on the syntax and the semantic level. Based on these findings, we investigate conditional syntax splitting for nonmonotonic inference with c-representations. Regarding single c-representations, we utilize the concept of selection strategies, and show that a straightforward property of the selection strategy leads to inference operators satisfying conditional syntax splittings. Furthermore, we show that c-inference taking all c-representations of a belief base into account also fully complies with conditional syntax splitting.

Choice constructs are an important part of the language of logic programming, yet the study of their semantics has been a challenging task. So far, only two-valued semantics have been studied, and the different proposals for such semantics have not been compared in a principled way. In this paper, an operator-based framework allow for the definition and comparison of different semantics in a principled way is proposed.

Approximation fixpoint theory (AFT) is an abstract and general algebraic framework for studying the semantics of nonmonotonic logics. It provides a unifying study of the semantics of different formalisms for nonmonotonic reasoning, such as logic programming, default logic and autoepistemic logic. In this paper, we extend AFT to dealing with non-deterministic constructs that allow to handle indefinite information, represented e.g. by disjunctive formulas. This is done by generalizing the main constructions and corresponding results of AFT to non-deterministic operators, whose ranges are sets of elements rather than single elements. The applicability and usefulness of this generalization is illustrated in the context of disjunctive logic programming.

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.

In formal argumentation, a distinction can be made between extension-based semantics, where sets of arguments are either (jointly) accepted or not, and ranking-based semantics, where grades of accept- ability are assigned to arguments. Another important distinction is that between abstract approaches, that abstract away from the content of arguments, and structured approaches, that specify a method of constructing argument graphs on the basis of a knowledge base. While ranking-based semantics have been extensively applied to abstract argumentation, few work has been done on ranking-based semantics for structured argumentation. In this paper, we make a systematic investigation into the be- haviour of ranking-based semantics applied to existing formalisms for structured argumentation. We show that a wide class of ranking-based semantics gives rise to so-called culpability measures, and are relatively robust to specific choices in argument construction methods.

We show that assumption-based argumentation frameworks, based on contrapositive logics and partially-ordered preference functions, provide a solid platform for argumentation-based reasoning. Two useful properties of the preference functions are identified (selectivity and max-lower-boundedness), and extended forms of attacks relations are supported (exists-attacks and forall-attacks), which assure several desirable properties and a variety of reasoning modes.

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.

For propositional beliefs, there are well-established connections between belief revision, defeasible conditionals, and nonmonotonic inference. In argumentative contexts, such connections have not yet been investigated. On the one hand, the exact relationship between formal argumentation and nonmonotonic inference relations is a research topic that keeps on eluding researchers despite recently intensified efforts, whereas argumentative revision has been studied in numerous works during recent years. In this paper, we show that relationships between belief revision, defeasible conditionals, and nonmonotonic inference similar to those in propositional logic hold in argumentative contexts as well. We first define revision operators for abstract dialectical frameworks, and use such revision operators to define dynamic conditionals by means of the Ramsey test. We show that such conditionals can be equivalently defined using a total preorder over three-valued interpretations, and study the inferential behaviour of the resulting conditional inference relations.

Abstract Approximation fixpoint theory (AFT) is an abstract and general algebraic framework for studying the semantics of non-monotonic logics. In recent work, AFT was generalized to non-deterministic operators, that is, operators whose range are sets of elements rather than single elements. In this paper, we make three further contributions to non-deterministic AFT: (1) we define and study ultimate approximations of non-deterministic operators, (2) we give an algebraic formulation of the semi-equilibrium semantics by Amendola et al., and (3) we generalize the characterizations of disjunctive logic programs to disjunctive logic programs with aggregates.

Abstract dialectical frameworks (in short, ADFs) are a unifying model of formal argumentation, where argumentative relations between arguments are represented by assigning acceptance conditions to atomic arguments. This idea is generalized by letting acceptance conditions being assigned to complex formulas, resulting in conditional abstract dialectical frameworks (in short, cADFs). We define the semantics of cADFs in terms of a non-truth-functional four-valued logic, and study the semantics in-depth, by showing existence results and proving that all semantics are generalizations of the corresponding semantics for ADFs.

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.

Abstract dialectical frameworks (in short, ADFs) are one of the most general and unifying approaches to formal argumentation. As the semantics of ADFs are based on three-valued interpretations, we ask which monotonic three-valued logic allows to capture the main semantic concepts underlying ADFs. We show that possibilistic logic is the unique logic that can faithfully encode all other semantical concepts for ADFs. Based on this result, we also characterise strong equivalence and introduce possibilistic ADFs.

Conditional independence is a crucial concept for efficient probabilistic reasoning. For symbolic and qualitative reasoning, however, it has played only a minor role. Recently, Lynn, Delgrande, and Peppas have considered conditional independence in terms of syntactic multivalued dependencies. In this paper, we define conditional independence as a semantic property of epistemic states and present axioms for iterated belief revision operators to obey conditional independence in general. We show that c-revisions for ranking functions satisfy these axioms, and exploit the relevance of these results for iterated belief revision in general.

Abstract Justification theory is a general framework for the definition of semantics of rule-based languages that has a high explanatory potential. Nested justification systems, first introduced by Denecker et al., allow for the composition of justification systems. This notion of nesting thus enables the modular definition of semantics of rule-based languages, and increases the representational capacities of justification theory. As we show in this paper, the original characterization of semantics for nested justification systems leads to the loss of information relevant for explanations. In view of this problem, we provide an alternative characterization of their semantics and show that it is equivalent to the original one. Furthermore, we show how nested justification systems allow representing fixpoint definitions.

Extension-based semantics in abstract argumentation provide a criterion to determine whether a set of arguments is acceptable or not. In this paper, we present the notion of extension-ranking semantics, which determines a preordering over sets of arguments, where one set is deemed more plausible than another if it is somehow more acceptable. We obtain extension-based semantics as a special case of this new approach, but it also allows us to make more fine-grained distinctions, such as one set being "more complete'' or "more admissible'' than another. We define a number of general principles to classify extension-ranking semantics and develop concrete approaches. We also study the relation between extension-ranking semantics and argument-ranking based semantics, which rank individual arguments instead of sets of arguments.

Approximation fixpoint theory (AFT) constitutes an abstract and general algebraic framework for studying the semantics of nonmonotonic logics. It provides a unifying study of the semantics of different formalisms for nonmonotonic reasoning, such as logic programming, default logic and autoepistemic logic. In this paper, we extend AFT to non-deterministic constructs such as disjunctive information. This is done by generalizing the main constructions and corresponding results to non-deterministic operators, whose ranges are sets of elements rather than single elements. The applicability and usefulness of this generalization is illustrated in the context of disjunctive logic programming.

For propositional beliefs, there are well-established connections between belief revision, defeasible conditionals and nonmonotonic inference. In argumentative contexts, such connections have not yet been investigated. On the one hand, the exact relationship between formal argumentation and nonmonotonic inference relations is a research topic that keeps on eluding researchers despite recently intensified efforts, whereas argumentative revision has been studied in numerous works during recent years. In this paper, we show that similar relationships between belief revision, defeasible conditionals and nonmonotonic inference hold in argumentative contexts as well. We first define revision operators for abstract dialectical frameworks, and use such revision operators to define dynamic conditionals by means of the Ramsey test. We show that such conditionals can be equivalently defined using a total preorder over three-valued interpretations, and study the inferential behaviour of the resulting conditional inference relations.

We present a formal argumentation system for dealing with the detachment of prioritized conditional obligations and permissions. In the presence of facts and constraints, we answer the question whether an unconditional obligation or permission is detachable by considering arguments for and against its detachment. For the evaluation of arguments in favour of detachment, we use a Dung-style argumentation-theoretical semantics. We illustrate how violations and contrary-to-duty scenarios are dealt with in our framework and pay special attention to conflict-resolution via priorities.

We investigate Dung's semantics for assumption-based frameworks (ABFs) that are induced by contrapositive logics. We show that unless the falsity propositional constant is part of the defeasible assumptions, the grounded semantics lacks most of the desirable properties it has in abstract argumentation frameworks (AAFs), and that for simple definitions of the contrariness operator and the attacks relations, preferred and stable semantics are reduced to naive semantics. We also show the tight relations of this framework to reasoning with maximally consistent sets, and consider some properties of the induced entailments, such as being cumulative or preferential relations that satisfy non-interference.

In structured argumentation frameworks such as ASPIC+, rebuts are only allowed in conclusions produced by defeasible rules. This has been criticized as counter-intuitive especially in dialectical contexts. In this paper we show that ASPIC-, a system allowing for unrestricted rebuts, suffers from contamination problems. We remedy this shortcoming by generalizing the attack rule of unrestricted rebut. Our resulting system satisfies the usual rationality postulates for prioritized rule bases.