We present an infinite-game characterization of the well-founded semantics for function-free logic programs with negation. Our game is a simple generalization of the standard game for negation-less logic programs intr...
详细信息
We present an infinite-game characterization of the well-founded semantics for function-free logic programs with negation. Our game is a simple generalization of the standard game for negation-less logic programs introduced by van Emden [M.H. van Emden, Quantitative deduction and its fixpoint theory, Journal of logicprogramming 3 (1) (1986) 37-53] in which two players, the Believer and the Doubter, compete by trying to prove (respectively disprove) a query. The standard game is equivalent to the minimum Herbrand model semantics of logic programming in the sense that a query succeeds in the minimum model semantics iff the Believer has a winning strategy for the game which begins with the Doubter doubting this query. The game for programs with negation that we propose follows the same rules as the standard one, except that the players swap roles every time the play "passes through" negation. We start our investigation by establishing the determinacy of the new game by using some classical tools from the theory of infinite-games. Our determinacy result immediately provides a novel and purely. game-theoretic characterization of the semantics of negation in logicprogramming. We proceed to establish the connections of the game semantics to the existing semantic approaches for logicprogramming with negation. For this purpose, we first define a refined version of the game that uses degrees of winning and losing for the two players. We then demonstrate that this refined game corresponds exactly to the infinite-valued minimum model semantics of negation [P. Rondogiannis,W.W. Wadge, Minimum model semantics for logic programs with negation-as-failure, ACM Transactions on Computational logic 6 (2) (2005) 441-467]. This immediately implies that the unrefined game is equivalent to the well-founded semantics (since the infinite-valued semantics is a refinement of the well-founded semantics). (c) 2007 Elsevier B.V. All rights reserved.
We propose a framework of autoepistemic reasoning in which the underlying semantics is determined by the choice of a nonmonotonic inference mechanism and by specifying a belief constraint. While the latter makes the a...
详细信息
We propose a framework of autoepistemic reasoning in which the underlying semantics is determined by the choice of a nonmonotonic inference mechanism and by specifying a belief constraint. While the latter makes the approach flexible in meeting possibly different applications, the former links the resulting semantics to a nonmonotonic reasoning formalism and thus allows adoption of existing techniques. In this paper we choose circumscription as the underlying inference mechanism and use two different belief constraints to define two semantics, the stable circumscriptive semantics and the well-founded circumscriptive semantics, for autoepistemic theories. The former coincides with Moore's autoepistemic logic for logic programs and is arguably more desirable in handling disjunctive autoepistemic theories. The latter is a reconstruction and extension of Przymusinski's iterative method for computing the least AEL(circ) expansions for logic programs. We show that for logic programs the two construction methods coincide. However, while Przymusinski's construction method is restricted to logic programs only, the well-founded circumscriptive semantics is applicable to more general autoepistemic theories.
We present a fixed point theorem for a class of (potentially) non-monotonic functions over specially structured complete lattices. The theorem has as a special case the Knaster-Tarski fixed point theorem when restrict...
详细信息
We present a fixed point theorem for a class of (potentially) non-monotonic functions over specially structured complete lattices. The theorem has as a special case the Knaster-Tarski fixed point theorem when restricted to the case of monotonic functions and Kleene's theorem when the functions are additionally continuous. From the practical side, the theorem has direct applications in the semantics of negation in logicprogramming. In particular, it leads to a more direct and elegant proof of the least fixed point result of [12]. Moreover, the theorem appears to have potential for possible applications outside the logicprogramming domain. (C) 2015 Elsevier B.V. All rights reserved.
Two distinct research approaches have been proposed for assigning extensional semantics to higher-order logicprogramming. The former approach [11] uses classical domain theoretic tools while the latter [1] builds on ...
详细信息
Two distinct research approaches have been proposed for assigning extensional semantics to higher-order logicprogramming. The former approach [11] uses classical domain theoretic tools while the latter [1] builds on a fixed-point construction defined on a syntactic instantiation of the source program. The relationships between these two approaches had not been investigated until now. In this paper we demonstrate that for a very broad class of programs, namely the class of definitional programs introduced by W.W. Wadge, the two approaches coincide with respect to ground atoms that involve symbols of the program. On the other hand, we argue that if existential higher-order variables are allowed to appear in the bodies of program rules, the two approaches are in general different. The results of the paper contribute to a better understanding of the semantics of higher-order logicprogramming. (C) 2017 Elsevier B.V. All rights reserved.
The purpose of the present paper is to give an overview of our joint work with Zoltan Esik, namely the development of an abstract fixed point theory for a class of non-monotonic functions [4] and its use in providing ...
详细信息
The purpose of the present paper is to give an overview of our joint work with Zoltan Esik, namely the development of an abstract fixed point theory for a class of non-monotonic functions [4] and its use in providing a novel denotational semantics for a very broad extension of classical logicprogramming [1]. Our purpose is to give a high-level presentation of the main developments of these two works, that avoids as much as possible the underlying technical details, and which can be used as a mild introduction to the area.
暂无评论