×

zbMATH — the first resource for mathematics

Semantics of structured normal logic programs. (English) Zbl 1279.68190
Summary: In this paper we provide semantics for normal logic programs enriched with structuring mechanisms and scoping rules. Specifically, we consider constructive negation and expressions of the form \({Q} \supset {G}\) in goals, where \({Q}\) is a program unit, \({G}\) is a goal and \({\supset}\) stands for the so-called embedded implication. Allowing the use of these expressions can be seen as adding block structuring to logic programs. In this context, we consider static and dynamic rules for visibility in blocks. In particular, we provide new semantic definitions for the class of normal logic programs with both visibility rules. For the dynamic case we follow a standard approach. We first propose an operational semantics. Then, we define a model-theoretic semantics in terms of ordered structures which are a kind of intuitionistic Beth structures. Finally, an (effective) fixpoint semantics is provided and we prove the equivalence of these three definitions. In order to deal with the static case, we first define an operational semantics and then we present an alternative semantics in terms of a transformation of the given structured programs into flat ones. We finish by showing that this transformation preserves the computed answers of the given static program.
Reviewer: Reviewer (Berlin)
MSC:
68Q55 Semantics in the theory of computing
68N17 Logic programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Apt, K.; van Emden, M., Contributions to the theory of logic programming, J. ACM, 29, 841-862, (1982) · Zbl 0483.68004
[2] R. Arruabarrena, P. Lucio, M. Navarro, A strong logic programming view for static embedded implications, in: Proceedings of the Second International Conference on Foundations of Software Science and Computation Structures FOSSACS’99, LNCS, vol. 1578, Springer-Verlag, 1999, pp. 56-72. · Zbl 0948.68031
[3] M. Baldoni, L. Giordano, A. Martelli, Translating a modal language with embedded implication into Horn clause logic, in: Proceedings of the Fifth International Workshop on Extensions of Logic Programming, LNCS, vol. 1050, Springer-Verlag, 1996, pp. 19-33.
[4] A. Bonner, L.T. McCarty, Adding negation-as-failure to intuitionistic logic programming, in: Proceedings of the North American Conference on Logic Programming NACLP’90, MIT Press, 1990, pp. 681-703.
[5] Bossi, A.; Gabbrielli, M.; Levi, G.; Martelli, M., The s-semantics approach: theory and applications, J. logic programming, 19/20, 149-197, (1994) · Zbl 0942.68527
[6] Bugliesi, M.; Lamma, E.; Mello, P., Modularity in logic programming, J. logic programming, 19/20, 443-502, (1994)
[7] D. Chan, Constructive negation based on the completed database, in: Proceedings of the Fifth International Conference and Symposium on Logic Programming, MIT Press, 1988, pp. 111-125.
[8] D. Chan, An extension of constructive negation and its application in coroutining, in: Proceedings of the North American Conference on Logic Programming NACLP’89, MIT Press, 1989, pp. 477-493.
[9] Drabent, W., What is a failure? an approach to constructive negation, Acta inform., 32, 27-59, (1995) · Zbl 0815.68036
[10] Fages, F., Constructive negation by pruning, J. logic programming, 32, 85-118, (1997) · Zbl 0882.68034
[11] B. Freitag, Extending deductive database languages by embedded implications, in: Proceedings of the Third International Conference on Logic Programming and Automated Reasoning, LPAR’92, LNAI, vol. 624, Springer-Verlag, 1992, pp. 84-95.
[12] Gabbay, M., N-prolog: an extension of prolog with hypothetical implications II. logical foundations and negation as failure, J. logic programming, 1, 251-283, (1985) · Zbl 0595.68004
[13] Gabbay, M.; Reyle, U., N-prolog: an extension of prolog with hypothetical implications, J. logic programming, 1, 319-355, (1984) · Zbl 0576.68001
[14] Gelder, A.V.; Ross, K.A.; Schlipf, J.S., The well-founded semantics for general logic programs, J. ACM, 38, 3, 620-650, (1991) · Zbl 0799.68045
[15] M. Gelfond, V. Lifschitz, The stable model semantics for logic programming, in: ICLP/SLP, 1988, pp. 1070-1080.
[16] Giordano, L.; Martelli, A., Structuring logic programs: a modal approach, J. logic programming, 21, 59-94, (1994) · Zbl 0812.68065
[17] Giordano, L.; Martelli, A.; Rossi, G., Extending Horn clause logic with implication goals, Theoret. comput. sci., 95, 43-74, (1992) · Zbl 0754.68109
[18] Giordano, L.; Olivetti, N., Combining negation as failure and embedded implication in logic programs, J. logic programming, 36, 91-147, (1998) · Zbl 0911.68027
[19] Kunen, K., Negation in logic programming, J. logic programming, 4, 289-308, (1987) · Zbl 0655.68018
[20] Lloyd, J., Foundations of logic programming, (1987), Springer-Verlag · Zbl 0668.68004
[21] P. Lucio, Structured sequent calculi for combining intuitionistic and classical first-order logic, in: Proceedings of the Third International Workshop on Frontiers of Combining Systems, FroCoS ’00, LNAI, vol. 1974, Springer-Verlag, 2000, pp. 88-104. · Zbl 0961.03008
[22] Lucio, P.; Orejas, F.; Pino, E., An algebraic framework for the definition of compositional semantics of normal logic programs, J. logic programming, 40, 89-123, (1999) · Zbl 0933.68031
[23] McCarty, L., Clausal intuitionistic logic I. fixed point semantics, J. logic programming, 5, 1-31, (1988) · Zbl 0645.03006
[24] McCarty, L., Clausal intuitionistic logic II. tableau proof procedures, J. logic programming, 5, 93-132, (1988) · Zbl 0661.03004
[25] L. McCarty, A language for legal discourse I: Basic features, in: Proceedings of the ICAIL, vol. 89, 1989, pp. 180-189.
[26] Miller, D., A logical analysis of modules in logic programming, J. logic programming, 6, 79-108, (1989) · Zbl 0681.68022
[27] Nadathur, G.; Miller, D., Higher – order logic programming, (), 499-590 · Zbl 0900.68129
[28] M. Navarro, From modular Horn programs to flat ones: a formal proof for the propositional case, in: Proceedings of the Second International Symposium on Innovation in Information and Communication Technology, ISIICT, 2004.
[29] F. Orejas, E. Pasarella, E. Pino. Semantics of normal logic programs with embedded implications, in: Proceedings of the 17th International Conference on Logic Programming, ICLP 2001, LNCS, vol. 2237, Springer-Verlag, 2001, pp. 255-268. · Zbl 1053.68541
[30] Pasarella, E.; Orejas, F.; Pino, E.; Navarro, M., A transformational semantics of static embedded implications of normal logic programs, (), 133-146 · Zbl 1156.68329
[31] Przymusinski, T., On the declarative semantics of deductive databases and logic programs, (), 193-216 · Zbl 0726.68067
[32] T. Przymusinski, Every logic program has a natural stratification and an iterated least fixed point model, in: Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS ’89, ACM Press, 1989, pp. 11-21.
[33] T.C. Przymusinski, Perfect model semantics, in: ICLP/SLP, 1988, pp. 1081-1096.
[34] Shepherson, J., Negation in logic programming, (), 19-88
[35] Stuckey, P., Negation and constraint logic programming, Inform. and comput., 118, 12-33, (1995) · Zbl 0827.68022
[36] Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pacific J. math., 5, 285-309, (1955) · Zbl 0064.26004
[37] van Dalen, D., Intuitionistic logic, (), 1-114
[38] van Emden, M.; Kowalski, R., The semantics of predicate logic as a programming language, J. ACM, 23, 733-742, (1976) · Zbl 0339.68004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.