We analyze the complexity of reasoning with circumscribed low-complexity DLs such as DL-lite and the EL family, under suitable restrictions on the use of abnormality predicates. We prove that in circumscribed DL-lite R complexity drops from NExp NP to the second level of the polynomial hierarchy. In EL, reasoning remains ExpTime-hard, in general. However, by restricting the possible occurrences of existential restrictions, we obtain membership in Sigma p 2 and Pi p 2 for an extension of EL.

In the context of Dung's theory of abstract argumentation frameworks, the recently introduced resolution-based grounded semantics features the unique property of fully complying with a set of general requirements, only partially satisfied by previous literature proposals. This paper contributes to the investigation of resolution-based grounded semantics by analyzing its computational properties with reference to a standard set of decision problems for abstract argumentation semantics: (a) checking the property of being an extension for a set of arguments; (b) checking agreement with traditional grounded semantics; (c) checking the existence of a non-empty extension; (d) checking credulous acceptance of an argument; (e) checking skeptical acceptance of an argument. It is shown that problems (a)-(c) admit polynomial time decision processes, while (d) is NP-complete and (e) coNP-complete.

In rules considered in this paper, the conclusion may contain existentially quantified variables, which makes reasoning tasks (as deduction) non-decidable. These rules have the same logical form as TGD (tuple generating dependencies) in databases and as conceptual graph rules. We extend known decidable cases by combining backward and forward chaining schemes, in association with a graph that captures exactly the notion of dependency between rules. Finally, we draw a map of known decidable cases, including an extension obtained by combining our approach with very recent results on TGD.

In this article we discuss two alternative proposals for neighbourhood semantics (which we call strict and loose neighbourhood semantics, NSS and NSL respectively) that have been previously introduced in the literature. Our main tools are suitable notions of bisimulation. While an elegant notion of bisimulation exists for NSL, the required bisimulation for NSS is rather involved. We propose a simple extension of NSS with a universal modality that we call NSS(E), which comes together with a natural notion of bisimulation. We also investigate the complexity of the satisfiability problem for NSL and NSS(E).

Argumentation is a reasoning model based on the construction and evaluation of arguments. Dung has proposed an abstract argumentation framework in which arguments are assumed to have the same strength. This assumption is unfortunately not realistic. Consequently, three main extensions of the framework have been proposed in the literature. The basic idea is that if an argument is stronger than its attacker, the attack fails. The aim of the paper is twofold: First, it shows that the three extensions of Dung framework may lead to unintended results. Second, it proposes a new approach that takes into account the strengths of arguments, and that ensures sound results. We start by presenting two minimal requirements that any preference-based argumentation framework should satisfy, namely the conflict-freeness of arguments extensions and the generalization of Dung’s framework. Inspired from works on handling inconsistency in knowledge bases, the proposed approach defines a binary relation on the powerset of arguments. The maximal elements of this relation represent the extensions of the new framework.

Recent work on Alternating-Time Temporal Logic and Coalition Logic has allowed the expression of many interesting properties of coalitions and strategies. However there is no natural way of expressing resource requirements in these logics. This paper presents a Resource-Bounded Coalition Logic (RBCL) which has explicit representation of resource bounds in the language, and gives a complete and sound axiomatisation of RBCL.

Logic reasoning approaches to fault diagnosis account for the fact that a component c j may fail intermittently by introducing a parameter g j that expresses the probability the component exhibits correct behavior. This component parameter g j , in conjunction with a priori fault probability, is usedin a Bayesian framework to compute the posterior fault candidate probabilities. Usually, information on g j is not known a priori. While proper estimation of g j can have a great impact on the diagnostic accuracy, at present, only approximations have been proposed. We present a novel framework, BARINEL, that computes exact estimations of g j as integral part of the posterior candidate probability computation. BARINEL’s diagnostic performance is evaluated for both synthetic and real software systems. Our results show that our approach is superior to approaches based on classical persistent fault models as well as previously proposed intermittent fault models.

Qualitative Spatial and Temporal Reasoning (QSR) is concerned with constraint-based formalisms for representing, and reasoning with, spatial and temporal information over infinite domains.  Within the QSR community it has been a widely accepted assumption that genuine qualitative reasoning methods outperform other reasoning methods that are applicable to encodings of qualitative CSP instances. Recently this assumption has been tackled by several authors, who proposed to encode qualitative CSP instances as finite CSP or SAT instances. In this paper we report on the results of a broad empirical study in which we compared the performance of several reasoners on instances from different qualitative formalisms. Our results show that for small-sized qualitative calculi (e.g., Allen's interval algebra and RCC-8) a state-of-the-art implementation of QSR methods currently gives the most efficient performance. However, on recently suggested large-size calculi, e.g., OPRA4, finite CSP encodings provide a considerable performance gain. These results confirm a conjecture by Bessière stating that support-based constraint propagation algorithms provide better performance for large-sized qualitative calculi.

This paper presents a new analysis of dynamic constraint satisfaction problems (DCSPs) with finite domains and a new approach to solving them. We first show that even very small changes in a CSP, in the form of addition of constraints or changes in constraint relations, can have profound effects on search performance. These effects are reflected in the amenability of the problem to different forms of heuristic action as well as overall quality of search. In addition, classical DCSP methods perform poorly on these problems because there are sometimes no solutions similar to the original one found. We then show that the same changes do not markedly affect the locations of the major sources of contention in the problem. A technique for iterated sampling that performs a careful assessment of this property and uses the information during subsequent search, performs well even when it only uses information based on the original problem in the DCSP sequence. The result is a new approach to solving DCSPs that is based on a robust strategy for ordering variables rather than on robust solutions.

Optimization in graphical models is an important problem which has been studied in many AI frameworks such as weighted CSP, maximum satisfiability or probabilistic networks. By identifying conditionally independent subproblems, which are solved independently and whose optimum is cached, recent Branch and Bound algorithms offer better asymptotic time complexity. But the locality of bounds induced by decomposition often hampers the practical effects of this result because subproblems are often uselessly solved to optimality. Following the Russian Doll Search (RDS) algorithm, a possible approach to overcome this weakness is to (inductively) solve a relaxation of each subproblem to strengthen bounds. The algorithm obtained generalizes both RDS and tree-decomposition based algorithms such as BTD or AND-OR Branch and Bound. We study its efficiency on different problems, closing a very hard frequency assignment instance which has been open for more than 10 years.