Computing minimal models is an important task in Knowledge Representation and Reasoning that appears in formalisms such as circumscription, diagnosis and answer set programming. Even the most basic question of whether there exists a minimal model containing a given variable is known to be $\Sigma_2 P$-complete. In this work we study the problem of computing minimal models from the viewpoint of parameterized complexity theory. We perform an extensive complexity analysis of this problem with respect to eleven parameters. Tractable fragments based on combinations of these parameters are identified by giving several fixed-parameter algorithms. For the remaining combinations we show parameterized hardness results and thus prove that under usual complexity theoretic assumptions no further fixed-parameter algorithms exist for these parameters.

We analyze, along the lines of the knowledge compilation map, both the tractability and the succinctness of the propositional language URC of unit-refutation complete propositional formulae, as well as its disjunctive closure URC[V, ], and a superset of URC where variables can be existentially quantified and unit-refutation completeness concerns only consequences built up from free variables.

The stable model semantics treats a logic program as a mechanism for specifying its intensional predicates. In this paper we discuss a modification of that semantics in which functions, rather than predicates, are intensional. The idea of the new definition comes from nonmonotonic causal logic.

Invited Talks

Lecture in Remembrance of John McCarthy

Area Chairs and Program Committee

Conference Committee

In this paper, we address the problem of applying AGM-style belief revision to non-classical logics. We discuss the idea of minimal change in revision and show that for non-classical logics, some sort of minimality postulate has to be explicitly introduced. We also present two constructions for revision which satisfy the AGM postulates and prove the representation theorems including minimality postulates.

In this work we study action theories of the situation calculus such that the initial KB is a generalized database with equality constraints (GFDBs). We show that GFDBs characterize the class of definitional KBs and that they are closed under progression. We also show that, under conditions, generalized projection queries can be decided based on an induced transition system and evaluation of local conditions over states.

Aggregative deontic detachment is a new form of deontic detachment that keeps track of previously detached obligations. We argue that it handles iteration of successive detachments in a more principled manner than the traditional systems do. To study this new form of deontic detachment, we introduce a'minimal' logic for aggregative deontic detachment, and we discuss various properties of the logic.