Epistemic foundation of stable model semantics
Yann Loyer, Umberto Straccia
Logic programs Artificial Intelligence Hardware and Architecture Fixed-point semantics [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] Non-monotonic reasoning Computational Theory and Mathematics FOS: Computer and information sciences Artificial Intelligence (cs.AI) Theoretical Computer Science Software Stable model semantics Computer Science - Artificial Intelligence
Stable model semantics has become a very popular approach for the management of negation in logic programming. This approach relies mainly on the closed world assumption to complete the available knowledge and its formulation has its basis in the so-called Gelfond-Lifschitz transformation. The primary goal of this work is to present an alternative and epistemic-based characterization of stable model semantics, to the Gelfond-Lifschitz transformation. In particular, we show that stable model semantics can be defined entirely as an extension of the Kripke-Kleene semantics. Indeed, we show that the closed world assumption can be seen as an additional source of 'falsehood' to be added cumulatively to the Kripke-Kleene semantics. Our approach is purely algebraic and can abstract from the particular formalism of choice as it is based on monotone operators (under the knowledge order) over bilattices only.
Source: Theory and practice of logic programming 6 (2006): 355–393. doi:10.1017/S1471068405002619
Publisher: Cambridge University Press., Cambridge, Regno Unito
[7] Nuel D. Belnap. A useful four-valued logic. In Gunnar Epstein and J. Michael Dunn, editors, Modern uses of multiple-valued logic, pages 5-37. Reidel, Dordrecht, NL, 1977.
[8] H. Blair and V. S. Subrahmanian. Paraconsistent logic programming. Theoretical Computer Science, 68:135-154, 1989.
[9] K.L. Clark. Negation as failure. In Herv´e Gallaire and Jack Minker, editors, Logic and data bases, pages 293-322. Plenum Press, New York, NY, 1978.
[43] T. C. Przymusinski. Stationary semantics for disjunctive logic programs and deductive databases. In S. Debray and H. Hermenegildo, editors, Logic Programming, Proceedings of the 1990 North American Conference, pages 40-59. MIT Press, 1990.
[45] Raymond Reiter. On closed world data bases. In Herv´e Gallaire and Jack Minker, editors, Logic and data bases, pages 55-76. Plenum Press, New York, NY, 1978.
[46] Raymond Reiter. A logic for default reasoning. Artificial Intelligence, 13:81-132, 1980.
[47] A. Tarski. A lattice-theoretical fixpoint theorem and its applications. Pacific Journal of Mathematics, (5):285-309, 1955.
[48] Allen van Gelder. The alternating fixpoint of logic programs with negation. In Proc. of the 8th ACM SIGACT SIGMOD Sym. on Principles of Database Systems (PODS-89), pages 1-10, 1989.
[49] Allen van Gelder, Kenneth A. Ross, and John S. Schlimpf. The well-founded semantics for general logic programs. Journal of the ACM, 38(3):620-650, 1991.
Metrics
Back to previous page
@article{oai:it.cnr:prodotti:179888,
title = {Epistemic foundation of stable model semantics},
author = {Yann Loyer and Umberto Straccia},
publisher = {Cambridge University Press., Cambridge, Regno Unito},
doi = {10.1017/s1471068405002619 and 10.48550/arxiv.cs/0403002},
journal = {Theory and practice of logic programming},
volume = {6},
pages = {355–393},
year = {2006}
}
0000-0001-5998-6757
