Search

Standard answer set programming (ASP) targets at solving search problems from the first level of the polynomial time hierarchy (PH). Tackling search problems beyond NP using ASP is less straightforward. The class of disjunctive logic programs offers the most prominent way of reaching the second level of the PH, but encoding respective hard problems as disjunctive programs typically requires sophisticated techniques such as saturation or meta-interpretation. The application of such techniques easily leads to encodings that are inaccessible to non-experts. Furthermore, while disjunctive ASP solvers often rely on calls to a (co-)NP oracle, it may be difficult to detect from the input program where the oracle is being accessed. In other formalisms, such as Quantified Boolean Formulas (QBFs), the interface to the underlying oracle is more transparent as it is explicitly recorded in the quantifier prefix of a formula. On the other hand, ASP has advantages over QBFs from the modeling perspective. The rich high-levellanguages such as ASP-Core-2 offer a wide variety of primitives that enable concise and natural encodings of search problems. In this paper, we present a novel logic programming-based modeling paradigm that combines the best features of ASP and QBFs. We develop so-called combined logic programs in which oracles are directly cast as (normal) logic programs themselves. Recursive incarnations of this construction enable logic programming on arbitrarily high levels of the PH. We develop a proof-of-concept implementation for our new paradigm.

Several forms of reasoning in AI – like abduction, closed world reasoning, circumscription, and disjunctive logic programming – are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae or programs is bounded by some constant. Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction.

Standard answer set programming (ASP) targets at solving search problems from the first level of the polynomial time hierarchy (PH). Tackling search problems beyond NP using ASP is less straightforward. The class of disjunctive logic programs offers the most prominent way of reaching the second level of the PH, but encoding respective hard problems as disjunctive programs typically requires sophisticated techniques such as saturation or meta-interpretation. The application of such techniques easily leads to encodings that are inaccessible to non-experts. Furthermore, while disjunctive ASP solvers often rely on calls to a (co-)NP oracle, it may be difficult to detect from the input program where the oracle is being accessed. In other formalisms, such as Quantified Boolean Formulas (QBFs), the interface to the underlying oracle is more transparent as it is explicitly recorded in the quantifier prefix of a formula. On the other hand, ASP has advantages over QBFs from the modeling perspective. The rich high-level languages such as ASP-Core-2 offer a wide variety of primitives that enable concise and natural encodings of search problems. In this paper, we present a novel logic programming--based modeling paradigm that combines the best features of ASP and QBFs. We develop so-called combined logic programs in which oracles are directly cast as (normal) logic programs themselves. Recursive incarnations of this construction enable logic programming on arbitrarily high levels of the PH. We develop a proof-of-concept implementation for our new paradigm. This paper is under consideration for acceptance in TPLP., Comment: Paper presented at the 32nd International Conference on Logic Programming (ICLP 2016), New York City, USA, 16-21 October 2016, 16 pages, LaTeX, no figures

Default logics are usually used to describe the regular behavior and normal properties of domain elements. In this paper we suggest, conversely, that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected semantical characteristics. These sets of literals are selected among those explicitly embodied in the given knowledge base. Hence, essentially we perceive outlier detection as a knowledge discovery technique. This paper defines the notion of outlier in two related formalisms for specifying defaults: Reiter's default logic and extended disjunctive logic programs. For each of the two formalisms, we show that finding outliers is quite complex. Indeed, we prove that several versions of the outlier detection problem lie over the second level of the polynomial hierarchy. We believe that a thorough complexity analysis, as done here, is a useful preliminary step towards developing effective heuristics and exploring tractable subsets of outlier detection problems.

Disjunctive logic programming (DLP) with stable model semantics is a powerful nonmonotonic formalism for knowledge representation and reasoning. Reasoning with DLP is harder than with normal (∨-free) logic programs, because stable model checking—deciding whether a given model is a stable model of a propositional DLP program—is co-NP-complete, while it is polynomial for normal logic programs.This paper proposes a new transformation ΓM(P), which reduces stable model checking to UNSAT—i.e., to deciding whether a given CNF formula is unsatisfiable. The stability of a model M of a program P thus can be verified by calling a Satisfiability Checker on the CNF formula ΓM(P). The transformation is parsimonious (i.e., no new symbol is added), and efficiently computable, as it runs in logarithmic space (and therefore in polynomial time). Moreover, the size of the generated CNF formula never exceeds the size of the input (and is usually much smaller). We complement this transformation with modular evaluation results, which allow for efficient handling of large real-world reasoning problems.The proposed approach to stable model checking has been implemented in DLV—a state-of-the-art implementation of DLP. A number of experiments and benchmarks have been run using SATZ as Satisfiability checker. The results of the experiments are very positive and confirm the usefulness of our techniques.

In this thesis, we study denotational semantics (model-theoretic and game-theoretic) of four logic programming languages: - LP which is the most restrictive one; - DLP which extends LP by allowing disjunctions; - LPN which extends LP by allowing negations; and - DLPN which allows bothThe three main contributions of this dissertation can be summarized as follows: (1) An abstract framework for logic programming semantics is defined and all semantic approaches that we study are placed within this framework. We define the general notion of a truth value space as an appropriate algebraic structure that satisfies a set of axioms. The booleans form the canonical example of such a space, but we need to consider much more general ones when dealing with negation-as-failure. For this we define and study an infinite family of spaces, parametrized over an ordinal number. (2) A game semantics for LP was defined in 1986 and further studied in 1998. Then in 2005 it was extended for the case of LPN programs. Here a game semantics for DLP programs is developed in full detail; we prove that it is sound and complete with respect to the standard, minimal models semantics of Minker. (3) We define a semantic operator which transforms any given abstract semantics of a non-disjunctive language to a semantics of the"corresponding" disjunctive one. We exhibit the correctness of this transformation by proving that it preserves equivalences of semantics, and we present some applications of it, obtaining new game semantics for DLPN, among others.; Cette thèse s'intéresse à la sémantique dénotationnelle (en théorie des modèles et en théorie des jeux) de quatre langages de programmation logique: - LP, le plus restrictif de tous, - DLP, une extension de LP aux disjonctions, - LPN, une extension de LP aux négations, et - DLPN, qui inclut les deux.Ce manuscrit apporte trois contributions principales : (1) Un cadre abstrait pour la sémantique de la programmation logique y est défini, et toutes les approches sémantiques que nous étudions par la suite prennent place dans ce cadre. Nous définissons la notion générale d'espace de valeurs de vérité comme une structure algébrique spécifique, satisfaisant un certain ensemble d'axiomes. Les booléens forment l'exemple canonique d'un tel espace, mais nous devons étudier des cas plus généraux si nous voulons considérer la "négation par l'échec". Pour cela, nous définissons et étudions une famille infinie d'espaces, paramétrée par un ordinal. (2) Une sémantique des jeux pour LP a été définie en 1986, et son étude a été approfondie en 1998. Elle a ensuite été étendue au cas des programmes LPN en 2005. Ici nous développons en détails une sémantique pour les programmes DLP. Nous prouvons qu'elle est correcte et complète par rapport aux modèles minimaux de Minker. (3) Nous définissons un opérateur sémantique qui, étant donnée une sémantique abstraite d'un langage non disjonctif, la transforme en une sémantique disjonctive associée. La correction de cette transformation découle du fait qu'elle conserve les équivalences de sémantiques. Nous en présentons ensuite quelques applications qui permettent, entre autres, d'obtenir la première sémantique des jeux pour DLPN.

Abductive logic programming (ALP) and disjunctive logic programming (DLP) are two different extensions of logic programming. This paper investigates the relationship between ALP and DLP from the program transformation viewpoint. It is shown that the belief set semantics of an abductive program is expressed by the answer set semantics and the possible model semantics of a disjunctive program. In converse, the possible model semantics of a disjunctive program is equivalently expressed by the belief set semantics of an abductive program, while such a transformation is generally impossible for the answer set semantics. Moreover, it is shown that abductive disjunctive programs are always reducible to disjunctive programs both under the answer set semantics and the possible model semantics. These transformations are verified from the complexity viewpoint. The results of this paper turn out that ALP and DLP are just different ways of looking at the same problem if we choose an appropriate semantics.

International audience; Denotational semantics of logic programming and its extensions (by allowing negation, disjunctions, or both) have been studied thoroughly for many years. In 1998, a game semantics was given to definite logic programs by Di Cosmo, Loddo, and Nicolet, and a few years later it was extended to deal with negation by Rondogiannis and Wadge. Both approaches were proven equivalent to the traditional semantics. In this paper we define a game semantics for disjunctive logic programs and prove soundness and completeness with respect to the minimal model semantics of Minker. The overall development has been influenced by the games studied for PCF and functional programming in general, in the styles of Abramsky-­Jagadeesan-­Malacaria and Hyland-­Ong­-Nickau.

In this thesis we propose a new approach to deduction methods for temporal logic. Our proposal is based on an inductive definition of eventualities that is different from the usual one. On the basis of this non-customary inductive definition for eventualities, we first provide dual systems of tableaux and sequents for Propositional Linear-time Temporal Logic (PLTL). Then, we adapt the deductive approach introduced by means of these dual tableau and sequent systems to the resolution framework and we present a clausal temporal resolution method for PLTL. Finally, we make use of this new clausal temporal resolution method for establishing logical foundations for declarative temporal logic programming languages. The key element in the deduction systems for temporal logic is to deal with eventualities and hidden invariants that may prevent the fulfillment of eventualities. Different ways of addressing this issue can be found in the works on deduction systems for temporal logic. Traditional tableau systems for temporal logic generate an auxiliary graph in a first pass.Then, in a second pass, unsatisfiable nodes are pruned. In particular, the second pass must check whether the eventualities are fulfilled. The one-pass tableau calculus introduced by S. Schwendimann requires an additional handling of information in order to detect cyclic branches that contain unfulfilled eventualities. Regarding traditional sequent calculi for temporal logic, the issue of eventualities and hidden invariants is tackled by making use of a kind of inference rules (mainly, invariant-based rules or infinitary rules) that complicates their automation. A remarkable consequence of using either a two-pass approach based on auxiliary graphs or aone-pass approach that requires an additional handling of information in the tableau framework, and either invariant-based rules or infinitary rules in the sequent framework, is that temporal logic fails to carry out the classical correspondence between tableaux and sequents. In this thesis, we first provide a one-pass tableau method TTM that instead of a graph obtains a cyclic tree to decide whether a set of PLTL-formulas is satisfiable. In TTM tableaux are classical-like. For unsatisfiable sets of formulas, TTM produces tableaux whose leaves contain a formula and its negation. In the case of satisfiable sets of formulas, TTM builds tableaux where each fully expanded open branch characterizes a collection of models for the set of formulas in the root. The tableau method TTM is complete and yields a decision procedure for PLTL. This tableau method is directly associated to a one-sided sequent calculus called TTC. Since TTM is free from all the structural rules that hinder the mechanization of deduction, e.g. weakening and contraction, then the resulting sequent calculus TTC is also free from this kind of structural rules. In particular, TTC is free of any kind of cut, including invariant-based cut. From the deduction system TTC, we obtain a two-sided sequent calculus GTC that preserves all these good freeness properties and is finitary, sound and complete for PLTL. Therefore, we show that the classical correspondence between tableaux and sequent calculi can be extended to temporal logic. The most fruitful approach in the literature on resolution methods for temporal logic, which was started with the seminal paper of M. Fisher, deals with PLTL and requires to generate invariants for performing resolution on eventualities. In this thesis, we present a new approach to resolution for PLTL. The main novelty of our approach is that we do not generate invariants for performing resolution on eventualities. Our method is based on the dual methods of tableaux and sequents for PLTL mentioned above. Our resolution method involves translation into a clausal normal form that is a direct extension of classical CNF. We first show that any PLTL-formula can be transformed into this clausal normal form. Then, we present our temporal resolution method, called TRS-resolution, that extends classical propositional resolution. Finally, we prove that TRS-resolution is sound and complete. In fact, it finishes for any input formula deciding its satisfiability, hence it gives rise to a new decision procedure for PLTL. In the field of temporal logic programming, the declarative proposals that provide a completeness result do not allow eventualities, whereas the proposals that follow the imperative future approach either restrict the use of eventualities or deal with them by calculating an upper bound based on the small model property for PLTL. In the latter, when the length of a derivation reaches the upper bound, the derivation is given up and backtracking is used to try another possible derivation. In this thesis we present a declarative propositional temporal logic programming language, called TeDiLog, that is a combination of the temporal and disjunctive paradigms in Logic Programming. We establish the logical foundations of our proposal by formally defining operational and logical semantics for TeDiLog and by proving their equivalence. Since TeDiLog is, syntactically, a sublanguage of PLTL, the logical semantics of TeDiLog is supported by PLTL logical consequence. The operational semantics of TeDiLog is based on TRS-resolution. TeDiLog allows both eventualities and always-formulas to occur in clause heads and also in clause bodies. To the best of our knowledge, TeDiLog is the first declarative temporal logic programming language that achieves this high degree of expressiveness. Since the tableau method presented in this thesis is able to detect that the fulfillment of an eventuality is prevented by a hidden invariant without checking for it by means of an extra process, since our finitary sequent calculi do not include invariant-based rules and since our resolution method dispenses with invariant generation, we say that our deduction methods are invariant-free. CYCIT (ref. TIC98-0949-C02-02), CYCIT (ref. TIC2001-2476-C03-03), CYCIT (ref. TIN2004-07925-C03-03), CICYT (ref. TIN2007-66523), University of the Basque Country (ref. UPV-EHU GIU07/35), University of the Basque Country (ref. UFI11/45)

Περιέχει το πλήρες κείμενο In this paper we introduce the logic programming language Disjunctive Chronolog which combines the programming paradigms of temporal and disjunctive logic programming. Disjunctive Chronolog is capable of expressing dynamic behaviour as well as uncertainty, two notions that are very common in a variety of real systems. We present the minimal temporal model semantics and the fixpoint semantics for the new programming language and demonstrate their equivalence. We also show how proof procedures developed for disjunctive logic programs can be easily extended to apply to Disjunctive Chronolog programs.

The paper presents DLV+, a Disjunctive Logic Programming (DLP) system with object-oriented constructs, including classes, objects, (multiple) inheritance, and types. DLV+ is built on top of DLV (a state-of-the art DLP system), and provides a graphical user interface that allows one to specify, update, browse, query, and reason on knowledge bases. Two strong points of the system are the powerful type-checking mechanism and the advanced interface for visual querying.DLV+ is already used for the development of knowledge based applications for information extraction and text classification.

It was noted recently that the framework of default logics can be exploited for detecting outliers. Outliers are observations expressed by sets of literals that feature unexpected properties. These observations are not explicitly provided in input (as it happens with abduction) but, rather, they are hidden in the given knowledge base. Unfortunately, in the two related formalisms for specifying defaults — Reiter's default logic and extended disjunctive logic programs — the most general outlier detection problems turn out to lie at the third level of the polynomial hierarchy. In this note, we analyze the complexity of outlier detection for two very simple classes of default theories, namely NU and DNU, for which the entailment problem is solvable in polynomial time. We show that, for these classes, checking for the existence of an outlier is anyway intractable. This result contributes to further showing the inherent intractability of outlier detection in default reasoning.