This paper is set to study the applicability of AGM-like operations to probabilistic bases. We focus on the problem of consistency restoration, also called consolidation or contraction by falsity. We aim to identify the reasons why the set of AGM postulates based on discrete operations of deletions and accretions is too coarse to treat finely adjustable probabilistic formulas. We propose new principles that allow one to deal with the consolidation of inconsistent probabilistic bases, presenting a finer method called liftable contraction. Furthermore, we show that existing methods for probabilistic consolidation via distance minimization are particular cases of the methods proposed.

We survey a selection of inconsistency measures from the literature and investigate their computational complexity wrt. decision problems related to bounds on the inconsistency value and the functional problem of determining the actual value. Our findings show that those inconsistency measures can be partitioned into three classes related to their complexity. The first class contains measures whose complexity are located on the first level of the polynomial hierarchy, the second class contains measures on the second level of the polynomial hierarchy, and the third class is located beyond the second level of the polynomial hierarchy. We provide membership results for all the investigated problems and completeness results for most of them.

Lifting a recent proposal by Moreno-Centeno and Karp, we propose a general framework for so-called implicit hitting set algorithms for reasoning beyond NP. The framework is motivated by empirically successful specific instantiations of the approach---based on interactions between a Boolean satisfiability (SAT) solver and an integer programming (IP) solver---in the context of maximum satisfiability (MaxSAT). The framework opens up opportunities for developing implicit hitting set algorithms for various important reasoning problems in KR by implementing domain-specific reasoning modules with SAT and IP solvers. We detail instantiations of the framework for the minimum satisfiability problem---as a natural dual of MaxSAT---and, as a central KR problem, for propositional abduction, covering the second level of the polynomial hierarchy. We show empirically that an implementation of the instantiation for propositional abduction surpasses the efficiency of an approach based on encoding and solving propositional abduction instances as disjunctive logic programming under answer set semantics.We also study key properties of the general framework.

Knowledge compilation has been successfully used to solve beyond NP problems, including some PP-complete and NP PP -complete problems for Bayesian networks. In this work we show how knowledge compilation can be used to solve problems in the more intractable complexity class PP^PP.  This class contains NP PP and includes interesting AI problems, such as non-myopic value of information. We show how to solve the prototypical PP PP -complete problem MajMajsat in linear-time once the problem instance is compiled into a special class of Sentential Decision Diagrams. To show the practical value of our approach, we adapt it to answer the Same-Decision Probability (SDP) query, which was recently introduced for Bayesian networks. The SDP problem is also PP PP P-complete. It is a value-of-information query that quantifies the robustness of threshold-based decisions and comes with a corresponding algorithm that was also recently proposed. We present favorable experimental results, comparing our new algorithm based on knowledge compilation with the state-of-the-art algorithm for computing the SDP.

In this paper, we propose a general framework, both parameterized and parameter-free, for defining a family of fine-grained inconsistency measures for propositional knowledge bases. The parameterized approach allows to encompass several existing inconsistency mea- sures as specific cases, by properly setting its parameter. And the parameter-free approach is defined to avoid the difficulty in choosing a suitable parameter in practice but still keeps a desired ranking for knowledge bases by their inconsistency degrees. The fine granularity of our framework is based on the notion of MIS partition that considers the inner structure of all the minimal inconsistent subsets of a knowledge base. Moreover, MinCostSAT-based encodings are provided, which enable the use of efficient SAT solvers for the computation of the proposed measures. We implement these algo- rithms and test them on some real-world datasets. The preliminary experimental results for a variety of inputs show that the proposed framework gives a wide range of possibilities for evaluating large knowledge bases.

The formalisms for knowledge representation and reasoning(KR&R) typically have a variety of semantics, each one having its particular application scenarios. However, the KR&Rcommunity cannot readily benefit from such a variety due toa lack of efficient solver technology. This is partly caused bythe fact that solver development is laborious and even accomplishing a working prototype can form a major effort.In this paper, we introduce a new framework that enables us todeclaratively specify a given semantics in second-order logicand to automatically generate a solver from that specification. Hence, KR&R researchers can rapidly develop a solverprototype for their new/existing semantics with a minimal effort. Technically, our framework builds on a recent approachfor nesting SAT solvers based on lazy clause generation.We evaluate our framework in the context of Dung’s argumentation frameworks, logic programming, and propositionallogic subject to standard and non-standard semantics. Weshow for each of those formalisms that one can easily specify its semantics using a few second-order sentences and thatone can effectively obtain a solver for that semantics usingour automated solver generation procedure.For instance, in the case of argumentation frameworks, weobtain 16 different solvers, each solving one of four inference tasks for one of four major argumentation semantics andshow that our solvers (slightly) outperform the best solverfrom the last system competition despite not being tuned forargumentation instances.

IBIS (Issue Based Information System) provides a widely adopted approach for knowledge representation especially suitable for the challenging task of representing wicked decision problems. While many tools for visualisation and collaborative development of IBIS graphs are available, automated decision support in this context is still underdeveloped, even though it would benefit several applications. QuAD (Quantitative Argumentation Debate) frameworks are a recently proposed IBIS-based formalism encompassing automated decision support by means of an algorithm for quantifying the strength of alternative decision options, based on aggregation of the strength of their attacking and supporting arguments. The initially proposed aggregation method, however, may give rise to discontinuities. In this paper we propose a novel, discontinuity-free algorithm for computing the strength of decision options in QuAD frameworks. We prove that this algorithm features several desirable properties and we compare the two aggregation methods, showing that both may be appropriate in the context of different application scenarios.

We provide new insights into the area of combining abstract argumentation frameworks with probabilistic reasoning. In particular, we consider the scenario when assessments on the probabilities of a subset of the arguments is given and the probabilities of the remaining arguments have to be derived, taking both the topology of the argumentation framework and principles of probabilistic reasoning into account. We generalize this scenario by also considering inconsistent assessments, i.e., assessments that contradict the topology of the argumentation framework. Building on approaches to inconsistency measurement, we present a general framework to measure the amount of conflict of these assessments and provide a method for inconsistent-tolerant reasoning.

Abstract argumentation frameworks (AFs) are one of the central formalisms in AI; equipped with a wide range of semantics, they have proven useful in several application domains. We contribute to the systematic analysis of semantics for AFs by connecting two recent lines of research -- the work on input/output frameworks and the study of the expressiveness of semantics. We do so by considering the following question: given a function describing an input/output behaviour by mapping extensions (resp. labellings) to sets of extensions (resp. labellings), is there an AF with designated input and output arguments realizing this function under a given semantics? For the major semantics we give exact characterizations of the functions which are realizable in this manner.

Formalizing dynamics of argumentation has received increasing attention over the last years. While AGM-like representation results for revision of argumentation frameworks (AFs) are now available, similar results for the problem of merging are still missing. In this paper, we close this gap and adapt model-based propositional belief merging to define extension-based merging operators for AFs. We state an axiomatic and a constructive characterization of merging operators through a family of rationality postulates and a representation theorem. Then we exhibit merging operators which satisfy the postulates. In contrast to the case of revision, we observe that obtaining a single framework as result of merging turns out to be a more subtle issue. Finally, we establish links between our new results and previous approaches to merging of AFs, which mainly relied on axioms from Social Choice Theory, but lacked AGM-like representation theorems.