Abstract
Existing formalisations of (transfinite) inductive definitions in constructive mathematics are reviewed and strong correspondences with LP under least model and perfect model semantics become apparent. I point to fundamental restrictions of these existing formalisations and argue that the well-founded semantics (wfs) overcomes these problems and hence, provides a superior formalisation of the principle of inductive definition. The contribution of this study for LP is that it (re-) introduces the knowledge theoretic interpretation of LP as a logic for representing definitional knowledge. I point to fundamental differences between this knowledge theoretic interpretation of LP and the more commonly known interpretations of LP as default theories or auto-epistemic theories. The relevance is that differences in knowledge theoretic interpretation have strong impact on knowledge representation methodology and on extensions of the LP formalism, for example for representing uncertainty.
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
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addusin-Wesley Publishing Company, 1995.
P. Aczel. An Introduction to Inductive Definitions. In J. Barwise, editor, Handbook of Mathematical Logic, pages 739–782. North-Holland Publishing Company, 1977.
K.R. Apt, H.A. Blair, and A. Walker. Towards a theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann, 1988.
W. Buchholz, S. Feferman, and W. Pohlers W. Sieg. Iterated Inductive Definitions and Subsystems of Analysis: Recent Proof-Theoretical Studies. Springer-Verlag, Lecture Notes in Mathematics 897, 1981.
K.L. Clark. Negation as failure. In H. Gallaire and J. Minker, editors, Logic and Databases, pages 293–322. Plenum Press, 1978.
M. Denecker. A Terminological Interpretation of (Abductive) Logic Programming. In V.W. Marek, A. Nerode, and M. Truszczynski, editors, International Conference on Logic Programming and Nonmonotonic Reasoning, pages 15–29. Springer, Lecture notes in Artificial Intelligence 928, 1995.
M. Denecker and D. De Schreye. Justification semantics: a unifying framework for the semantics of logic programs. Technical Report 157, Department of Computer Science, K.U.Leuven, 1992.
M. Denecker and D. De Schreye. SLDNFA: an abductive procedure for abductive logic programs. Journal of Logic Programming, 34(2):111–167, 1997.
S. Feferman. Formal theories for transfinite iterations of generalised inductive definitions and some subsystems of analysis. In A. Kino, J. Myhill, and R.E. Vesley, editors, Intuitionism and Proof theory, pages 303–326. North Holland, 1970.
M. Fitting. A Kripke-Kleene Semantics for Logic Programs. Journal of Logic Programming, 2(4):295–312, 1985.
M. Gelfond. On Stratified Autoepistemic Theories. In Proc. of AAAI87, pages 207–211. Morgan Kaufman, 1987.
M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. In Proc. of the International Joint Conference and Symposium on Logic Programming, pages 1070–1080. IEEE, 1988.
M. Gelfond and V. Lifschitz. Logic Programs with Classical Negation. In D.H.D. Warren and P. Szeredi, editors, Proc. of the 7th International Conference on Logic Programming 90, page 579. MIT press, 1990.
M. Hagiya and T. Sakurai. Foundation of Logic Programming Based on Inductive Definition. New Generation Computing, 2:59–77, 1984.
G. Kreisel. Generalized inductive definitions. Technical report, Stanford University, 1963.
P. Martin-Löf. Hauptsatz for the intuitionistic theory of iterated inductive definitions. In J.e. Fenstad, editor, Proceedings of the Second Scandinavian Logic Symposium, pages 179–216, 1971.
J. McCarthy. Applications of Circumscription to Formalizing Common-Sense Knowledge. Artifical Intelligence, 28:89–116, 1980.
Y. N. Moschovakis. Elementary Induction on Abstract Structures. North-Holland Publishing Company, Amsterdam-New York, 1974.
E. Post. Formal reduction of the general combinatorial decision problem. American Journal of Mathematics, 65:197–215, 1943.
H. Przymusinska and T.C. Przymusinski. Weakly perfect model semantics for logic programs. In R.A. Kowalski and K.A. Bowen, editors, Proc. of the fifth international conference and symposium on logic programming, pages 1106–1120. the MIT press, 1988.
T.C. Przymusinski. On the semantics of Stratified Databases. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming. Morgan Kaufman, 1988.
T.C. Przymusinski. Well founded semantics coincides with three valued Stable Models. Fundamenta Informaticae, 13:445–463, 1990.
R. Reiter. The Frame Problem in the Situation Calculus: A simple Solution (Sometimes) and a Completeness Result for Goal Regression. In V. Lifschitz, editor, Artificial Intelligence and Mathematical Theory of Computation: Papers in Honour of John McCarthy, pages 359–380. Academic Press, 1991.
C. Spector. Inductively defined sets of natural numbers. In Infinitistic Methods (Proc. 1959 Symposium on Foundation of Mathematis in Warsaw), pages 97–102. Pergamon Press, Oxford, 1961.
K. Van Belleghem, M. Denecker, and D. De Schreye. A strong correspondence between description logics and open logic programming. In Lee Naish, editor, Proc. of the International Conference on Logic Programming, 1997, pages 346–360. MIT-press, 1997.
K. Van Belleghem, M. Denecker, and D. Theseider Dupré. Dependencies and ramifications in an event-based language. In Proc. of the Ninth Dutch Artificial Intelligence Conference, 1997, 1997.
M. van Emden and R.A Kowalski. The semantics of Predicate Logic as a Programming Language. Journal of the ACM, 4(4):733–742, 1976.
A. Van Gelder, K.A. Ross, and J.S. Schlipf. The Well-Founded Semantics for General Logic Programs. Journal of the ACM, 38(3):620–650, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Denecker, M. (1998). The Well-Founded Semantics Is the Principle of Inductive Definition. In: Dix, J., del Cerro, L.F., Furbach, U. (eds) Logics in Artificial Intelligence. JELIA 1998. Lecture Notes in Computer Science(), vol 1489. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49545-2_1
Download citation
DOI: https://doi.org/10.1007/3-540-49545-2_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65141-3
Online ISBN: 978-3-540-49545-1
eBook Packages: Springer Book Archive