Abstract
We present a compositional model-theoretic semantics for logic programs, where the composition of programs is modelled by the composition of the admissible Herbrand models of the programs. An Herbrand model is admissible if it is supported by the assumption of a set of hypotheses. On one hand, the hypotheses supporting a model correspond to an open interpretation of the program intended to capture possible compositions with other programs. On the other hand, admissible models provide a natural model-theory for a form of hypothetical reasoning, called abduction. The application of admissibel models to programs with negation is discussed.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Apt, K. R., “Logic Programming,” inHandbook of Theoretical Computer Science (J. van Leeuwen, ed.), Vol. B, Elsevier, pp. 493–574, 1990.
Apt, K. R. and van Emden, M. H., “Contributions to the Theory of Logic Programming,”Journal of the ACM, 29, 3, pp. 841–862, 1982.
Bossi, A., Gabbrielli, M., Levi, G., and Meo, M. C., “Contribution to the Semantics of Open Logic Programs,” inProceedings of FGCS92 (ICOT, ed.), pp. 570–580, Ohmsha, 1992.
Brogi, A., Lamma, E., Mancarella, P., and Mello, P., “Abductive Reasoning in a Multi-Theory Framework,” inTrends in Artificial Intelligence (S. Gaglio, ed.),Proceedings of the Second Congress of the Italian Association for Artificial Intelligence, Lecture Notes in Artificial Intelligences, 549, Palermo, Springer-Verlag, pp. 137–146, 1991.
Brogi, A., Lamma, E., Mancarella, P., and Mello, P., “Normal Logic Programs as Open Positive Programs” inProceedings 1992 Joint International Conference on Logic Programming (K. R. Apt and J. Minker, eds.) the MIT Press, 1992.
Brogi, A., Lamma, E., and Mello, P., “Open Logic Theories,” inProceedings of Second Workshop on Extensions of Logic Programming, Lectures Notes in Artificial Intelligence, H.-H. Eriksson, P. Krueger, and P. Schroeder-Heister, eds., Kista, Springer-Verlag, Jan. 1991.
Brogi, A., Mancarella, P., Pedreschi, D., and Turini, F., “Composition Operators for Logic Theories,” inComputational Logic (J. W. Lloyd, ed.),Symposium Proceedings, Springer-Verlag, 596, pp. 73–88 Brussels, pp. 117–134, Nov. 1990.
Charniak, E. and McDermott, D.,Introduction to Artificial Intelligence, Addison-Wesely, 1985.
Clark, K., “Negation as Failure,” inLogic and Data Bases (H. Gallaire and J. Minker, eds.), Plenum, pp. 293–322, 1978.
Dung, P. M., “Negation as Hypothesis: An Abductive Foundation for Logic Programming,” inProc. 8th International Conference on Logic Programming (K. Furukawa, ed.), The MIT Press, pp. 3–17, 1991.
Eshgi, K. and Kowalski, R. A., “Abduction Compared with Negation by Failure,” inProc. Sixth International Conference on Logic Programming (G. Levi and M. Martelli, eds.), The MIT Press, pp. 234–254, 1989.
Gaifman, H. and Shapiro, E., “Fully Abstract Compositional Semantics for Logic Programs,” inProc. Sixteenth POPL, pp. 134–142, 1989.
Gelfond, M. and Lifschitz, V., “The Stable Models Semantics for Logic Programs,” inProc. Fifth International Conference on Logic Programming (R. A. Kowalski and K. A. Bowen, eds.), The MIT Press, pp. 1070–1080, 1988.
Kakas, A. C. and Mancarella, P., “Generalized Stable Models: a Semantics for Abduction,” inProceedings of 9th European Conference on Artificial Intelligence (L. Carlucci Aiello, ed.) Pitman, pp. 385–391, 1990.
Kowalski, R. A., “Problems and Promises of Computational Logic,” inComputational Logic, Symposium Proceedings (J. W. Lloyd, ed.), Springer-Verlag, Brussels, pp. 1–36, Nov. 1990.
Lloyd, J. W.,Foundations of Logic Programming, second edition, Springer-Verlag, 1987.
Mancarella, P. and Pedreschi, D., “An Algebra of Logic Programs,” inProc. Fifth International Conference on Logic Programming (R. A. Kowalski and K. A. Bowen, eds.), The MIT Press, pp. 1006–1023, 1988.
Mancarella, P., Pedreschi, D., Rondinelli, M., and Tagliatti, M., “Algebraic Properties of a Class of Logic Programs,” inProc. NACLP (S. Debray and M. Hermenegildo, eds.), The MIT Press, pp. 23–49, 1990.
Miller, D., “A Logical Analysis of Modules in Logic Programming,”Journal of Logic Programming, 6, pp. 79–108, 1989.
Monteiro, L. and Porto, A., “Contextual Logic Programming,” inProc. Sixth International Conference on Logic Programming (G. Levi and M. Martelli, eds.), The MIT Press, pp. 284–302, 1989.
O’Keefe, R., “Towards an Algebra for Constructing Logic Prograams,” inProceedings of IEEE Symposium on Logic Programming (J. Cohen and J. Conery, eds.), IEEE Computer Society Press, pp. 152–160, 1985.
Poole, D., “Compiling a Default Reasoning System into Prolog,”New Generation Computing, 9, 1, pp. 3–38, 1991.
Poole, D. L., “A Logical Framework for Default Reasoning,”Artificial Intelligence, 36, pp. 27–47, 1988.
Przymusinski, T. C., “Extended Stable Semantics for Normal and Disjunctive Programs,” inProc. 7th International Conference on Logic Programming (D. H. D. Warren and P. Szeredi, eds.), The MIT Press, pp. 459–477, 1990.
Przymusinski, T. C., “Semantics of Disjunctive Logic Programs and Deductive Databases,” inProc. DOOD91 (C. Delobel, M. Kifer and Y. Masunaga, eds.), Springer-Verlag, pp. 85–107, 1991.
Reiter, R., “On Closed World Data Bases,” inLogic and Data Bases (Gallaire and J. Minker, eds.), Plenum, pp. 293–322, 1978.
Sacca, D. and Zaniolo, C., “Stable Models and Nondeterminism in Logic Programs with Negation,” inProc. 9th ACM Symp. on Principles of Database Systems, ACM, pp. 205–217, 1990.
Sacca, D. and Zaniolo, C., “Partial Models and Three-Valued Models in Logic Programs with Negation,” inProc. Workshop on Logic Programming and Non-Monotonic Reasoning, The MIT Press, pp. 87–101, 1991.
van Emden, M. H. and Kowalski, R. A., “The Semantics of Predicate Logic as a Programming Language,”Journal of the ACM, 23, 4, pp. 733–742, 1976.
Van Gelder, A., Ross, K. A., and Schlipf, J. S., “Unfounded Sets and the Well-Founded Semantics of General Logic Programs,” inProc. ACM SIGMODSIGACT Symp. on Principles of Database Systems, ACM, pp. 221–230, 1988.
Author information
Authors and Affiliations
Additional information
Antonio Brogi: Dipartimento di Informatica, Università di Pisa, Corso Italia 40, 56125 Pisa, ItalyResearch interests: Programming Language Design and Semantics, Logic Programming and Artificial Intelligence
Evelina Lamma, Ph. D.: Associate Professor, The University of Udine, (Present Address) Dipartimento di Electronica, Informatica e Sistemistica, Università di Bologna, Viale Risorgimento 2, 40136 Bologna, ItalyResearch interests: Programming Languages and Knowledge Representation, with particular reference to Logic Languages and their extentions.
Paola Mello, Ph. D.: Associate Professor, Dipartimento di Electronica, Informatica e Sistemistica, Università di Bologna, Viale Risorgimento 2, 40136 Bologna, ItalyResearch interests: Programming Languages and Knowledge Representation, with particular reference to theoretical and practical aspects of extentions of Logic Programming
About this article
Cite this article
Brogi, A., Lamma, E. & Mello, P. Compositional model-theoretic semantics for logic programs. New Gener Comput 11, 1–21 (1992). https://doi.org/10.1007/BF03037525
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF03037525