Abstract
Approximation Fixpoint Theory was developed as a fixpoint theory of lattice operators that provides a uniform formalization of four main semantics of three major nonmonotonic reasoning formalisms. This paper clarifies how this fixpoint theory can define the stable and well-founded semantics of logic programs. It investigates the notion of strong equivalence underlying this semantics. It also shows the remarkable power of this theory for defining natural and elegant versions of these semantics for extensions of logic and answer set programs. In particular, we here consider extensions with general rule bodies, general interpretations (also non-Herbrand interpretations) and aggregates. We also investigate the relationship with the equilibrium semantics of nested answer set programs, on the formal and the informal level.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Belnap, N.D.: A useful four-valued logic. In: Dunn, J.M., Epstein, G. (eds.) Modern Uses of Multiple-Valued Logic, pp. 8–37. Reidel, Dordrecht (1977); Invited papers from the Fifth International Symposium on Multiple-Valued Logic, held at Indiana University, Bloomington, Indiana, May 13-16 (1975)
Clark, K.L.: Negation as failure. In: Logic and Data Bases, pp. 293–322. Plenum Press (1978)
Denecker, M., Marek, V.W., Truszczyński, M.: Approximating operators, stable operators, well-founded fixpoints and applications in non-monotonic reasoning. In: Logic-based Artificial Intelligence. The Kluwer International Series in Engineering and Computer Science, pp. 127–144. Kluwer Academic Publishers, Boston (2000)
Denecker, M., Marek, V.W., Truszczynski, M.: Uniform semantic treatment of default and autoepistemic logics. Artif. Intell. 143(1), 79–122 (2003)
Eiter, T., Fink, M., Tompits, H., Traxler, P., Woltran, S.: Replacements in non-ground answer-set programming. In: Doherty, P., Mylopoulos, J., Welty, C.A. (eds.) KR, pp. 340–351. AAAI Press (2006)
Feferman, S.: Toward useful type-free theories. Journal of Symbolic Logic 49(1), 75–111 (1984)
Fitting, M.: A Kripke-Kleene semantics for logic programs. Journal of Logic Programming 2(4), 295–312 (1985)
Fitting, M.: Fixpoint semantics for logic programming a survey. Theoretical Computer Science 278(1-2), 25–51 (2002)
Gelfond, M.: Representing Knowledge in A-Prolog. In: Kakas, A.C., Sadri, F. (eds.) Computational Logic: Logic Programming and Beyond. LNCS (LNAI), vol. 2408, pp. 413–451. Springer, Heidelberg (2002)
Gelfond, M., Lifschitz, V.: The stable model semantics for logic programming. In: Kowalski, R.A., Bowen, K.A. (eds.) ICLP/SLP, pp. 1070–1080. MIT Press (1988)
Janhunen, T., Oikarinen, E., Tompits, H., Woltran, S.: Modularity aspects of disjunctive stable models. J. Artif. Intell. Res (JAIR) 35, 813–857 (2009)
Kleene, S.C.: Introduction to Metamathematics. Van Nostrand (1952)
Lifschitz, V., Pearce, D., Valverde, A.: Strongly equivalent logic programs. ACM Trans. Comput. Log. 2(4), 526–541 (2001)
Lin, F., Chen, Y.: Discovering classes of strongly equivalent logic programs. J. Artif. Intell. Res (JAIR) 28, 431–451 (2007)
Marek, V.W., Truszczyński, M.: Logic programs with abstract constraint atoms. In: Proceedings of the 19th National Conference on Artificial Intelligence (AAAI 2004), pp. 86–91. AAAI Press (2004)
Pearce, D.: A New Logical Characterisation of Stable Models and Answer Sets. In: Dix, J., Przymusinski, T.C., Moniz Pereira, L. (eds.) NMELP 1996. LNCS, vol. 1216, pp. 57–70. Springer, Heidelberg (1997)
Pearce, D.: Equilibrium logic. Ann. Math. Artif. Intell. 47(1-2), 3–41 (2006)
Pelov, N., Denecker, M., Bruynooghe, M.: Well-founded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming (TPLP) 7(3), 301–353 (2007)
Przymusinski, T.C.: The well-founded semantics coincides with the three-valued stable semantics. Fundamenta Informaticae 13(4), 445–463 (1990)
Van Gelder, A.: The alternating fixpoint of logic programs with negation. Journal of Computer and System Sciences 47(1), 185–221 (1993)
Van Gelder, A., Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. Journal of the ACM 38(3), 620–650 (1991)
Vennekens, J., Mariën, M., Wittocx, J., Denecker, M.: Predicate introduction for logics with a fixpoint semantics. Part I: Logic programming. Fundamenta Informaticae 79(1-2), 187–208 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Denecker, M., Bruynooghe, M., Vennekens, J. (2012). Approximation Fixpoint Theory and the Semantics of Logic and Answers Set Programs. In: Erdem, E., Lee, J., Lierler, Y., Pearce, D. (eds) Correct Reasoning. Lecture Notes in Computer Science, vol 7265. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30743-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-642-30743-0_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30742-3
Online ISBN: 978-3-642-30743-0
eBook Packages: Computer ScienceComputer Science (R0)