Impressive work has been done in the last years concerning the meaning of negation and disjunction in logic programs, but most of this research concentrated on propositional programs only. While it suffices to conside...
详细信息
Impressive work has been done in the last years concerning the meaning of negation and disjunction in logic programs, but most of this research concentrated on propositional programs only. While it suffices to consider the propositional case for investigating general properties and the overall behavior of a semantics, we feel that for real applications and for computational purposes an implementation should be able to handle first-order programs without grounding them. In this paper we present a theoretical framework by defining a calculus of program transformations that apply directly to rules with variables and function symbols. Our main results are that (a) this calculus is weakly confluent for arbitrary programs (ie., it has the normal form property), (b) it is weakly terminating for Datalog(V,inverted left perpendicular) programs, (c) for finite ground programs it is equivalent to a weakly terminating calculus introduced by Brass and Dix (1995), and (d) it approximates a generalization of Disjunctive Well-founded semantics (D-WFS) for arbitrary programs. We achieve this by transforming program rules into rules with equational constraints thereby using heavily methods and techniques from constraint logicprogramming (CLP). In particular, disconnection-methods play a crucial role. In principle, any constraint theory known from CLP can be exploited in the context of non-monotonic reasoning, not only equational constraints over the Herbrand domain. However, the respective constraint solver must be able to treat negative constraints of the considered constraint domain. Tn summary, this work yields the basis for a general combination of two paradigms: constraint logicprogramming andnon-monotonic reasoning. (C) 1995 Elsevier Science Inc. All rights reserved.
We suggest a general logical formalism for logicprogramming (called a biconsequence relation) based on a four-valued inference. We show that it forms a proper setting for representing logic programs of a most general...
详细信息
ISBN:
(纸本)3540628436
We suggest a general logical formalism for logicprogramming (called a biconsequence relation) based on a four-valued inference. We show that it forms a proper setting for representing logic programs of a most general kind and for describing fogies and semantics that characterize their behavior. In this way we also extend the connection between logic andlogicprogramming beyond positive programs. A uniform representation of various semantics for logic programs is presented. The main conclusion from this representation is that the distinction between these semantics can be largely attributed to the difference in their underlying (monotonic) logical systems. Moreover, in most cases the difference can even be reduced to that of the language, that is, to the difference in the logical connectives allowed for representing derivable information. In addition, it allows us to see a reasoning about logic programs as a most simple kind of nonmonotonic reasoning in general.
In this paper we propose a modal approach for reasoning about actions in a logicprogramming framework. We introduce a modal language which makes use of abductive assumptions to deal with persistency, and provides a s...
详细信息
ISBN:
(纸本)3540628436
In this paper we propose a modal approach for reasoning about actions in a logicprogramming framework. We introduce a modal language which makes use of abductive assumptions to deal with persistency, and provides a solution to the ramification problem, by allowing one-way "causal rules" to be defined among fluents. We define the abductive semantics of the language and a goal directed abductive proof procedure to compute abductive solutions for a goal from a given domain description. Both the semantics and the procedure are defined within the argumentation framework. In particular, we focus on a specific semantics, which is essentially an extension of Dung's admissibility semantics to a modal setting. The proof procedure is proved to be sound with respect to this semantics.
Impressive work has been done in the last;years concerning the meaning of negation and disjunction in logic programs, but most of this research concentrated on propositional programs only. While it suffices to conside...
详细信息
ISBN:
(纸本)3540628436
Impressive work has been done in the last;years concerning the meaning of negation and disjunction in logic programs, but most of this research concentrated on propositional programs only. While it suffices to consider the propositional case for investigating general properties and the overall behaviour of a semantics, we feel that for real applications and for computational purposes an implementation should be able to handle first-order programs without grounding them. In this paper we present a theoretical framework by defining a calculus of program transformations that apply directly to rules with variables and function symbols. Our main results are that (1) this calculus is confluent for arbitrary programs, (2) for finite ground programs it is equivalent to a terminating calculus introduced by Brass and Dir (1995), and (3) it approximates a generalisation of D-WFS for arbitrary programs. We achieve this by transforming program rules into rules with equational constraints thereby using heavily methods and techniques from constraint logicprogramming. In particular, disconnection-methods play a crucial role. In principle, any constraint theory known from the field of constraint logicprogramming can be exploited in the context of nonmonotonic reasoning, not only equational constraints over the Herbrand domain. However, the respective constraint solver must be able to treat negative constraints of the considered constraint domain. In summary, this work yields the basis for a general combination of two paradigms: constraint logicprogramming andnon-monotonic reasoning.
We present a bottom-up algorithm for the computation of the well-founded model of non-disjunctive logic programs. Our method is based on the elementary program transformations studied by BRASS and Dnr [6, 7]. However,...
详细信息
ISBN:
(纸本)3540628436
We present a bottom-up algorithm for the computation of the well-founded model of non-disjunctive logic programs. Our method is based on the elementary program transformations studied by BRASS and Dnr [6, 7]. However, their "residual program" can grow to exponential size, whereas for function-free programs our "program remainder" is always polynomial in the size, i.e. the number of tuples, of the extensional database (EDB). As in the SLG-resolution of CHEN and WARREN [11, 12, 13], we do not only delay negative but also positive literals if they depend on delayed negative literals. When disregarding goal-directedness, which needs additional concepts, our approach can be seen as a simplified bottom-up version of SLG-resolution applicable to range-restricted Datalog programs. Since our approach is also closely related to the alternating fixpoint procedure [27, 28], it can possibly serve as a basis for an integration of the resolution-based, fixpoint-based, and transformation-based evaluation methods.
The present prolegomena consist, as all indeed do, in a critical discussion serving to introduce and interpret the extended works that follow in this book. As a result, the book is not a mere collection of excellent p...
详细信息
Set-grouping and aggregation are powerful non-monotonic operations of practical interest in database query languages. We consider the problem of expressing aggregation via negation as failure (NF). We study this probl...
详细信息
ISBN:
(纸本)3540628436
Set-grouping and aggregation are powerful non-monotonic operations of practical interest in database query languages. We consider the problem of expressing aggregation via negation as failure (NF). We study this problem in the framework of partial-order clauses introduced in [JOM95]. We show a translation of partial-order programs to normal programs that is very natural: Any cost-monotonic partial-order program P becomes a stratified normal program transl(P) such that the declarative semantics of P is equivalent to the stratified semantics of transl(P). The ability to effect such a translation is significant because the resulting normal programs do not make any explicit use of the aggregation capability, yet they are concise and intuitive. The success of this translation is due to the fact that the translated program is a stratified normal program. That would not be the case for other more general classes of programs than cost-monotonic partial-order programs. We therefore investigate a second land more natural) translation that does not require the translated programs to be stratified, but requires the use of a suitable NF strategy. The class of normal programs originating from this translation is itself interesting. Every program in this class has a clear intended total model, although these programs are in general not stratified and not even call-consistent and do not have a stable model. The partial model given by the well-founded semantics is consistent with the intended total model and the extended well founded semantics WFS+ indeed defines the intended model. Since there is a well-defined and efficient operational semantics for partial-order programs [JOM95, JM95] we conclude that the gap between expression of a problem and computing its solution can be reduced with the right level of notation.
The purpose of this paper is to argue that nonmonotonic reasoning in general can be viewed as monotonic inferences constrained by a simple notion of priority constraint. More important, these type of constrained infer...
详细信息
作者：
Ruet, PaulLIENS
Ecole Normale Supérieure 45 rue d’Ulm Paris75005 France Thomson-LCR
Domaine de Corbeville Orsay91404 France
This paper investigates logical characterizations of some aspects of concurrent constraint (cc) computations. It contains both negative and positive results. We show that intuitionistic logic enables to observe the so...
详细信息
The proceedings contain 21 papers. The special focus in this conference is on Languages, Expressiveness of Spatial Languages. The topics include: Expressiveness of spatial languages;an informal introduction to constra...
ISBN:
(纸本)3540625011
The proceedings contain 21 papers. The special focus in this conference is on Languages, Expressiveness of Spatial Languages. The topics include: Expressiveness of spatial languages;an informal introduction to constraint database systems;query evaluation as constraint search;computing the well-founded semantics for constraint extensions of datalog;decomposition and lossless join in constraint databases;a rule-based CQL for 2-dimensional tables;on the expressiveness of query languages with linear constraints;on expressing topological connectivity in spatial datalog;the C3 constraint object-oriented database system;integrity constraint checking in chimera;techniques and implementation;a temporal constraint system for object-oriented databases;using database versions to implement temporal integrity constraints;genomic database applications in DISCO;constraint databases and program analysis using abstract interpretation;querying indexed files;on the complexity of BV-tree updates;implementing index data structures using constraint logicprogramming;problem solving in the disco constraint database system and a semantic query optimization algorithm for object-oriented databases.
暂无评论