Abstract Answer Set Programming (ASP) is a successful method for solving a range of real-world applications. Despite the availability of fast ASP solvers, computing answer sets demands significant computational resources, since the problem tackled is on the second level of the polynomial hierarchy. Answer set computation can be accelerated if the program is split into two disjoint parts, bottom and top. Thus, the bottom part is evaluated independently of the top part, and the results of the bottom part evaluation are used to simplify the top part. Lifschitz and Turner have introduced the concept of a splitting set, that is, a set of atoms that defines the splitting. In a previous paper, the notion of g-splitting set , which generalize the concept of splitting sets for disjunctive logic programs, was introduced. In this paper, we further investigate the topic of splitting sets and g-splitting sets. We show that the set inclusion problem for splitting sets can be reduced to a classic Search Problem and solved in polynomial time. We also show that the task of computing g-splitting sets with desirable properties is relatively easy and straightforward. Finally, we show that stable models can be decomposed to models of rules inspired by g-splitting sets and models of the rest of the program. This interesting property can assist in incremental computation of stable models.

Metaquerying is a data mining technology by which hidden dependencies among several database relations can be discovered. This tool has already been successfully applied to several real-world applications, but only preliminary results about the complexity of metaquerying can be found in the literature. In this article, we define several variants of metaquerying that encompass, as far as we know, all the variants that have been defined in the literature. We study both the combined complexity and the data complexity of these variants. We show that under the combined complexity measure metaquerying is generally intractable (unless P = NP ), lying sometimes quite high in the complexity hierarchies (as high as NP PP ), depending on the characteristics of the plausibility index. Nevertheless, we are able to single out some tractable and interesting metaquerying cases, whose combined complexity is LOGCFL-complete. As for the data complexity of metaquerying, we prove that, in general, it is within TC 0 , but lies within AC 0 in some simpler cases. Finally, we discuss the implementation of metaqueries by providing algorithms that answer them.

Metaquerying is a datamining technology by which hidden dependencies among several database relations can be discovered. This tool has already been successfully applied to several real-world applications. Recent papers provide only very preliminary results about the complexity of metaquerying. In this paper we define several variants of metaquerying that encompass, as far as we know, all variants defined in the literature. We study both the combined complexity and the data complexity of these variants. We show that, under the combined complexity measure, metaquerying is generally intractable (unless P=NP), but we are able to single out some tractable interesting metaquerying cases (whose combined complexity is LOGCFL-complete). As for the data complexity of metaquerying, we prove that, in general, this is in P, but lies within AC0 in some interesting cases. Finally, we discuss the issue of equivalence between metaqueries, which is useful for optimization purposes.

Reasoning with minimal models is at the heart of many knowledge-representation systems. Yet it turns out that this task is formidable, even when very simple theories are considered. In this paper, we introduce the elimination algorithm, which performs, in linear time, minimal model finding and minimal model checking for a significant subclass of positive CNF theories which we call positive head-cycle-free (HCF) theories. We also prove that the task of minimal entailment is easier for positive HCF theories than it is for the class of all positive CNF theories. Finally, we show how variations of the elimination algorithm can be applied to allow queries posed on disjunctive deductive databases and disjunctive default theories to be answered in an efficient way.

We show here that meta-variables of Prolog admit a simple declarative interpretation. This allows us to extend the usual theory of SLD-resolution to the case of logic programs with meta-variables, and to establish soundness and strong completeness of

Finding the stable models of a knowledge base is a significant computational problem in artificial intelligence. This task is at the computational heart of truth maintenance systems, autoepistemic logic, and default logic. Unfortunately, it is NP-hard. In this paper we present a hierarchy of classes of knowledge bases, Omega_1,Omega_2,..., with the following properties: first, Omega_1 is the class of all stratified knowledge bases; second, if a knowledge base Pi is in Omega_k, then Pi has at most k stable models, and all of them may be found in time O(lnk), where l is the length of the knowledge base and n the number of atoms in Pi; third, for an arbitrary knowledge base Pi, we can find the minimum k such that Pi belongs to Omega_k in time polynomial in the size of Pi; and, last, where K is the class of all knowledge bases, it is the case that union{i=1 to infty} Omega_i = K, that is, every knowledge base belongs to some class in the hierarchy.

Introduces a logic endowed with a two-place modal connective that has the intended meaning of "if /spl alpha/, then normally /spl beta/". On top of providing a well defined tool for analyzing common default reasoning, such a logic allows nesting of the default operator. We present a semantic framework in which many of the known default proof systems can be naturally characterized, and prove soundness and completeness theorems for several such proof systems. Our semantics is a "neighborhood modal semantics", and it allows for subjective defaults, i.e. defaults may vary within different worlds that belong to the same model. The semantics has an appealing intuitive interpretation and may be viewed as a set theoretic generalization of the probabilistic interpretations of default reasoning. We show that our semantics is general in the sense that any modal semantics that is sound for some basic axioms for default reasoning is a special case of our semantics. Such a generality result may serve to provide a semantical analysis of the relative strengths of different proof systems and to show the nonexistence of semantics with certain properties.>