We present a unifying approach to the efficient evaluation of propositional answer-set programs. Our approach is based on backdoors which are small sets of atoms that represent "clever reasoning shortcuts" through the search space. The concept of backdoors is widely used in the areas of propositional satisfiability and constraint satisfaction. We show how this concept can be adapted to the nonmonotonic setting and how it allows to augment various known tractable subproblems, such as the evaluation of Horn and acyclic programs. In order to use backdoors we need to find them first. We utilize recent advances in fixed-parameter algorithmics to detect small backdoors. This implies fixed-parameter tractability of the evaluation of propositional answer-set programs, parameterized by the size of backdoors. Hence backdoor size provides a structural parameter similar to the treewidth parameter previously considered. We show that backdoor size and treewidth are incomparable, hence there are instances that are hard for one and easy for the other parameter. We complement our theoretical results with first empirical results.

We consider an extension of the propositional modal logic S4 which allows <> to act not only on isolated formulas, but also on sets of formulas. The interpretation of <>A is then given by the tangled closure of the valuations of formulas in A, which over finite transitive, reflexive models indicates the existence of a cluster satisfying A. This extension has been shown to be more expressive than the basic modal language: for example, it is equivalent to the bisimulation-invariant fragment of FOL over finite S4 models, whereas the basic modal language is weaker. However, previous analyses of this logic have been entirely semantic, and no proof system was available. In this paper we present a sound proof system for the polyadic S4 and prove that it is complete. The axiomatization is fairly standard, adding only the fixpoint axioms of the tangled closure to the usual S4 axioms. The proof proceeds by explicitly constructing a finite model from a consistent set of formulas.

Defeasible inheritance networks are a non-monotonic framework that deals with hierarchical knowledge. On the other hand, rational closure is acknowledged as a landmark of the preferential approach. We will combine these two approaches and define a new non-monotonic closure operation for propositional knowledge bases that combines the advantages of both. Then we redefine such a procedure for Description Logics, a family of logics well-suited to model structured information. In both cases we will provide a simple reasoning method that is build on top of the classical entailment relation.

Multi-context systems (MCS) are a powerful framework for interlinking heterogeneous knowledge sources. They model the flow of information among different reasoning components (called contexts) in a declarative way, using so-called bridge rules, where contexts and bridge rules may be nonmonotonic. We considerably generalize MCS to managed MCS (mMCS): while the original bridge rules can only add information to contexts, our generalization allows arbitrary operations on context knowledge bases to be freely defined, e.g., deletion or revision operators. The paper motivates and introduces the generalized framework and presents several interesting instances. Furthermore, we consider inconsistency management in mMCS and complexity issues.

One criticism often advanced against abstract argumentation frameworks (AFs), is that these consider only one form of interaction between atomic arguments: specifically that an argument attacks another. Attempts to broaden the class of relationships include bipolar frameworks, where arguments support others, and abstract dialectical frameworks (ADFs). The latter, allow "acceptance'' of an argument, x, to be predicated on a given propositional function, C_x, dependent on the corresponding acceptance of its parents, i.e. those y for which occurs. Although offering a richly expressive formalism subsuming both standard and bipolar AFs, an issue that arises with ADFs is whether this expressiveness is achieved in a manner that would be infeasible within standard AFs. Can the semantics used in ADFs be mapped to some AF semantics? How many arguments are needed in an AF to "simulate'' an ADF? We show that (in a formally defined sense) any ADF can be simulated by an AF of similar size and that this translation can be realised by a polynomial time algorithm.

It is well-known that satisfiability (and hence validity) in the minimal classical modal logic is a PSPACE-complete problem. In this paper we consider the satisfiability and validity problems (here they are not dual, although mutually reducible) for the minimal modal logic over a finite Lukasiewicz chain, and show that they also are PSPACE-complete. This result is also true when adding either the Delta operator or truth constants in the language, i.e. in all these cases it is PSPACE-complete.

We analyze the complexity of reasoning in EL with defeasible inclusions, and extend previous results by tightening lower and upper complexity bounds and by relaxing some syntactic restrictions. We further extend the old framework by supporting arbitrary priority relations over defeasible inclusions.

Possibilistic logic is a well-known framework for dealing with uncertainty and reasoning under inconsistent knowledge bases. Standard possibilistic logic expressions are propositional logic formulas associated with positive real degrees belonging to [0,1]. However, in practice it may be difficult for an expert to provide exact degrees associated with formulas of a knowledge base. This paper proposes a flexible representation of uncertain information where the weights associated with formulas are in the form of intervals. We first study a framework for reasoning with interval-based possibilistic knowledge bases by extending main concepts of possibilistic logic such as the ones of necessity and possibility measures. We then provide a characterization of an interval-based possibilistic logic base by means of a concept of compatible standard possibilistic logic bases. We show that interval-based possibilistic logic extends possibilistic logic in the case where all intervals are singletons. Lastly, we provide computational complexity results of deriving plausible conclusions from interval-based possibilistic bases and we show that the flexibility in representing uncertain information is handled without extra computational costs.

In a seminal paper, Lin and Reiter introduced the notion of progression of basic action theories. Unfortunately, progression is second-order in general. Recently, Liu and Lakemeyer improve on earlier results and show that for the local-effect and normal actions case, progression is computable but may lead to an exponential blow-up. Nevertheless, they show that for certain kinds of expressive first-order knowledge bases with disjunctive information, called proper+, it is efficient. However, answering queries about the resulting state is still undecidable. In this paper, we continue this line of research and extend proper+ to include functions. We prove that their progression wrt local-effect, normal actions, and range-restricted theories, is first-order definable and efficiently computable. We then provide a new logically sound and complete decision procedure for certain kinds of queries.

We provide reformulations and generalizations of both the semantics of logic programs by Faber, Leone and Pfeifer and its extension to arbitrary propositional formulas by Truszczynski. Unlike the previous definitions, our generalizations refer neither to grounding nor to fixpoints, and apply to first-order formulas containing aggregate expressions. In the same spirit as the first-order stable model semantics proposed by Ferraris, Lee and Lifschitz, the semantics proposed here are based on syntactic transformations that are similar to circumscription. The reformulations provide useful insights into the FLP semantics and its relationship to circumscription and the first-order stable model semantics.