Search

Several forms of iterable belief change exist, differing in the kind of change and its strength: some operators introduce formulae, others remove them; some add formulae unconditionally, others only as additions to the previous beliefs; some only relative to the current situation, others in all possible cases. A sequence of changes may involve several of them: for example, the first step is a revision, the second a contraction and the third a refinement of the previous beliefs. The ten operators considered in this article are shown to be all reducible to three: lexicographic revision, refinement, and severe withdrawal. In turn, these three can be expressed in terms of lexicographic revision at the cost of restructuring the sequence. This restructuring needs not to be done explicitly: an algorithm that works on the original sequence is shown. The complexity of mixed sequences of belief change operators is also analyzed. Most of them require only a polynomial number of calls to a satisfiability checker, some are even easier.

We report complexity results about redundancy of formulae in 2CNF form. We first consider the problem of checking redundancy and show some algorithms that are slightly better than the trivial one. We then analyze problems related to finding irredundant equivalent subsets (I.E.S.) of a given set. The concept of cyclicity proved to be relevant to the complexity of these problems. Some results about Horn formulae are also shown., Comment: Corrected figures on Theorem 10; added and modified some references

A consistency default is a propositional inference rule that asserts the consistency of a formula in its consequence. Consistency defaults allow for a straightforward encoding of domains in which it is explicitely known when something is possible. The logic of consistency defaults can be seen as a variant of cumulative default logic or as a generalization of justified default logic; it is also able to simulate Reiter default logic in the seminormal case. A semantical characterization of consistency defaults in terms of processes and in terms of a fixpoint equation is given, as well as a normal form.

The complexity of deciding equivalence of a formula to an extension of a default theory is investigated for the Reiter, justified, constrained, and rational semantics.

We analyze the complexity of deciding whether a propositional interpretation is a model of a default theory for some of the variants of default logic presented in the literature: Reiter's, justified, constrained, rational, and cumulative. We prove that all the analyzed variants are Σp2-complete in the general case, and remains so even if all defaults are prerequisite-free and seminormal. Cumulative default logic is also Σp2-complete even if all defaults are normal and prerequisite-free. The other semantics are Δp2[log n]-complete and coNP-complete if all defaults are normal and prerequisites are allowed or not, respectively.

This article reports complexity results on diagnosis of systems modeled as graphs. In this model introduced by Rao and Viswanadham, each component is a node of a graph, and an edge indicates that faults propagate from one component to the other one. The basic problem of diagnosis is known to be polynomial and NP-complete in the cases of single faults and multiple faults, respectively. We extend the complexity analysis to the case of faulty alarms, and also consider the problem of limiting the propagation of faults. We show that none of the considered diagnosis problems can be simplified by preprocessing the graph. © 2005 Wiley Periodicals, Inc. Int J Int Syst 20: 1053–1076, 2005.

Some computationally hard problems, e.g., deduction in logical knowledge bases– are such that part of an instance is known well before the rest of it, and remains the same for several subsequent instances of the problem. In these cases, it is useful to preprocess off-line this known part so as to simplify the remaining on-line problem. In this paper we investigate such a technique in the context of intractable, i.e., NP-hard, problems. Recent results in the literature show that not all NP-hard problems behave in the same way: for some of them preprocessing yields polynomial-time on-line simplified problems (we call them compilable), while for other ones their compilability implies some consequences that are considered unlikely. Our primary goal is to provide a sound methodology that can be used to either prove or disprove that a problem is compilable. To this end, we define new models of computation, complexity classes, and reductions. We find complete problems for such classes, “completeness” meaning they are “the less likely to be compilable.” We also investigate preprocessing that does not yield polynomial-time on-line algorithms, but generically “decreases” complexity. This leads us to define “hierarchies of compilability,” that are the analog of the polynomial hierarchy. A detailed comparison of our framework to the idea of “parameterized tractability” shows the differences between the two approaches.

Several methods have been proposed as an attempt to deal with dynamically changing scenarios. From a computational point of view, different formalisms have different computational properties. In this article we consider knowledge bases represented as sets of Horn clauses. The importance of this case is twofold: first, inference is polynomial, thus tractable; second, Horn clauses represents causal relations between facts, thus they are of great practical importance, although not all propositional knowledge bases can be represented in Horn form. The complexity of Horn revision is still high, and in some cases coincides with the complexity of the general (non-Horn) case. We analyze the complexity of belief revision from the point of view of the compilation [Cadoli et al. 1999]: we study the possibility of reducing the complexity by allowing a (possibly expensive) preprocessing of part of the input of the problem. Extending the work of Cadoli et al.[1996], we consider the problem of compact representation of revision in the Horn case, i.e., given a knowledge base T and an update P (both represented by Horn clauses) decide whether T * P , the result of the revision, can be represented with a propositional formula whose size is polynomial in the size of T and P . We give this representation for all formalisms for which it exists, and we show that the existence of a compact representation is related to the possibility of decreasing the complexity of a formalism via a proprocessing.

Knowledge-based systems must be able to "intelligently" manage a large amount of information coming from different sources and at different moments in time. Intelligent systems must be able to cope with a changing world by adopting a "principled" strategy. Many formalisms have been put forward in the artificial intelligence (AI) and database (DB) literature to address this problem. Among them, belief revision is one of the most successful frameworks to deal with dynamically changing worlds. Formal properties of belief revision have been investigated by Alchourron, Gardenfors, and Makinson, who put forward a set of postulates stating the properties that a belief revision operator should satisfy. Among these properties, a basic assumption of revision is that the new piece of information is totally reliable and, therefore, must be in the revised knowledge base. Different principles must be applied when there are two different sources of information and each one has a different view of the situation-the two views contradicting each other. If we do not have any reason to consider any of the sources completely unreliable, the best we can do is to "merge" the two views in a new and consistent one, trying to preserve as much information as possible. We call this merging process arbitration. In this paper, we investigate the properties that any arbitration operator should satisfy. In the style of Alchourron, Gardenfors, and Makinson we propose a set of postulates, analyze their properties, and propose actual operators for arbitration.

A knowledge base is redundant if it contains parts that can be inferred from the rest of it. We study the problem of checking whether a CNF formula (a set of clauses) is redundant, that is, it contains clauses that can be derived from the other ones. Any CNF formula can be made irredundant by deleting some of its clauses: what results is an irredundant equivalent subset (I.E.S.) We study the complexity of some related problems: verification, checking existence of a I.E.S. with a given size, checking necessary and possible presence of clauses in I.E.S.'s, and uniqueness. We also consider the problem of redundancy with different definitions of equivalence., Comment: Extended and revised version of a paper that has been presented at ECAI 2002

Independence—the study of what is relevant to a given problem of reasoning—is an important AI topic. In this paper, we investigate several notions of conditional independence in propositional logic: Darwiche and Pearl's conditional independence, and some more restricted forms of it. Many characterizations and properties of these independence relations are provided. We show them related to many other notions of independence pointed out so far in the literature (mainly formula-variable independence, irrelevance and novelty under various forms, separability, interactivity). We identify the computational complexity of conditional independence and of all these related independence relations.