Applying GSATto Non-Clausal Formulas

Journal of Artificial Intelligence Research

In this pap er w e describ e ho w to mo dify GSA T so that it can b e applied to non-clausal form ulas. The idea is to use a particular \score" function whic h giv es the n um b er of clauses of the CNF con v ersion of a form ula whic h are false under a giv en truth assignmen t. Its v alue is computed in linear time, without constructing the CNF con v ersion itself. The prop osed metho dology applies to most of the v arian ts of GSA T prop osed so far. 1. GSA T has b een sho wn to solv e man y \hard" problems m uc h more e cien tly than other traditional algorithms lik e, e.g., DP (Da vis & Putnam, 1960). Since GSA T applies only to clausal form ulas, using it to nd mo dels for ordinary prop ositional form ulas requires some previous clausal-form con v ersion.


New Polynomial Classes for Logic-Based Abduction

arXiv.org Artificial Intelligence

We address the problem of propositional logic-based abduction, i.e., the problem of searching for a best explanation for a given propositional observation according to a given propositional knowledge base. We give a general algorithm, based on the notion of projection; then we study restrictions over the representations of the knowledge base and of the query, and find new polynomial classes of abduction problems.


Preferred extensions as stable models

arXiv.org Artificial Intelligence

Given an argumentation framework AF, we introduce a mapping function that constructs a disjunctive logic program P, such that the preferred extensions of AF correspond to the stable models of P, after intersecting each stable model with the relevant atoms. The given mapping function is of polynomial size w.r.t. AF. In particular, we identify that there is a direct relationship between the minimal models of a propositional formula and the preferred extensions of an argumentation framework by working on representing the defeated arguments. Then we show how to infer the preferred extensions of an argumentation framework by using UNSAT algorithms and disjunctive stable model solvers. The relevance of this result is that we define a direct relationship between one of the most satisfactory argumentation semantics and one of the most successful approach of non-monotonic reasoning i.e., logic programming with the stable model semantics.


Propositional Independence - Formula-Variable Independence and Forgetting

arXiv.org Artificial Intelligence

Independence -- the study of what is relevant to a given problem of reasoning -- has received an increasing attention from the AI community. In this paper, we consider two basic forms of independence, namely, a syntactic one and a semantic one. We show features and drawbacks of them. In particular, while the syntactic form of independence is computationally easy to check, there are cases in which things that intuitively are not relevant are not recognized as such. We also consider the problem of forgetting, i.e., distilling from a knowledge base only the part that is relevant to the set of queries constructed from a subset of the alphabet. While such process is computationally hard, it allows for a simplification of subsequent reasoning, and can thus be viewed as a form of compilation: once the relevant part of a knowledge base has been extracted, all reasoning tasks to be performed can be simplified.


Stream Reasoning on Expressive Logics

arXiv.org Artificial Intelligence

Data streams occur widely in various real world applications. The research on streaming data mainly focuses on the data management, query evaluation and optimization on these data, however the work on reasoning procedures for streaming knowledge bases on both the assertional and terminological levels is very limited. Typically reasoning services on large knowledge bases are very expensive, and need to be applied continuously when the data is received as a stream. Hence new techniques for optimizing this continuous process is needed for developing efficient reasoners on streaming data. In this paper, we survey the related research on reasoning on expressive logics that can be applied to this setting, and point to further research directions in this area.