Orejas, Fernando; Pino, Elvira; Ehrig, Hartmut Institutions for logic programming. (English) Zbl 0901.68027 Theor. Comput. Sci. 173, No. 2, 485-511 (1997). Summary: The compositionality of the semantics of logic programs with respect to (different varieties of) program union has been studied recently by a number of researchers. The approaches used can be considered quite ad hoc in the sense that they provide, from scratch, the semantic constructions needed to ensure compositionality and, in some cases, full abstraction in the given framework. In this paper, we study the application of general algebraic methods for obtaining, systematically, this kind of results. In particular, the method proposed consists in studying the adequate institution for describing the given class of logic programs and, then, in using general institution-independent results to prove compositionality and full abstraction. This is done in detail for the class of definite logic programs with respect to three kinds of composition operations: \(\Omega\)-union, standard union and module composition. In addition two different institutions are considered: the standard institution of Horn clause logic and a new institution that better captures the input/output operational behaviour of logic programs. Finally, a similar solution is sketched for other classes of logic programs. Cited in 3 Documents MSC: 68N17 Logic programming Keywords:Horn clause logic PDFBibTeX XMLCite \textit{F. Orejas} et al., Theor. Comput. Sci. 173, No. 2, 485--511 (1997; Zbl 0901.68027) Full Text: DOI References: [1] Apt, K. R., Logic Programming, (Handbook of Theoretical Computer Science, Vol B (1990), Elsevier: Elsevier Amsterdam), Ch. 10 · Zbl 1023.03018 [2] Barr, M.; Wells, C., Category Theory for Computing Science (1990), Prentice- Hall: Prentice- Hall Englewood Cliffs, NJ · Zbl 0714.18001 [3] Bossi, A.; Gabbrielli, M.; Levi, G.; Meo, M. C., Contributions to the semantics of open logics programs, (Proc. 5th Gen. Comp. Syst. (1992)), 570-580 · Zbl 0868.68018 [4] Burstall, R. M.; Goguen, J. A., The semantics of Clear, a specification language, (Proc. Copenhagen Winter School on Abstract Software Specification. Proc. Copenhagen Winter School on Abstract Software Specification, Lecture Notes in Computer Science, Vol. 86 (1980), Springer: Springer Berlin), 292-332 · Zbl 0456.68024 [5] Chan, D., Constructive negation based on the completed database, (Proc. 5th Interent. Conf. and Symp. on Logic Programming. Proc. 5th Interent. Conf. and Symp. on Logic Programming, Seattle (1988)), 111-125 [7] Ehrig, H.; Baldamus, M.; Orejas, F., New concepts for amalgamation and extension in the framework of specification logics, (Rozenberg, G.; Salomaa, A., Current Trends in Theoretical Computer Science (1993), Word Scientific: Word Scientific Singapore) [8] Ehrig, H.; Mahr, B., Fundamentals of Algebraic Specification 1 (1985), Springer: Springer Berlin · Zbl 0557.68013 [9] Ehrig, H.; Mahr, B., Fundamentals of Algebraic Specification 2 (1989), Springer: Springer Berlin · Zbl 0557.68013 [10] Ehrig, H.; Orejas, F.; Cornelius, F.; Baldamus, M., Abstract and behaviour module specifications, (Report 93-25 (1993), Tech. Univ: Tech. Univ Berlin) · Zbl 0923.68089 [11] Ehrig, H.; Pepper, P.; Orejas, F., On recent trends in algebraic specification, (Proc. ICALP’89. Proc. ICALP’89, Lecture Notes in Computer Science, Vol. 372 (1989), Springer: Springer Berlin), 263-288 · Zbl 0689.68013 [12] Falaschi, M.; Levi, G.; Martelli, M.; Palamidessi, C., Declarative modeling of the operational behaviour of logic languages, Theoret. Comput. Sci., 289-318 (1989) · Zbl 0699.68113 [13] Gabbrielli, M.; Levi, G., On the semantics of logic programs, (Leach, J.; Monien, B.; Rodriguez-Artalejo, M., Proc. ICALP 91. Proc. ICALP 91, Lecture Notes in Computer Science, Vol. 510 (1991), Springer: Springer Berlim), 1-19 · Zbl 0769.68013 [14] Gaifman, H.; Shapiro, E., Fully abstract compositional semantics for logics programs, (Proc. 16th Ann. ACM Symp. on Principles of Programming Languages (1989)), 134-142 [15] Gaifman, H.; Shapiro, E., Proof theory and semantics of logic programs, (Proc. 4th IEEE Symp. on Logic in Computer Science (1989)), 50-62 [16] Goguen, J. A.; Burstall, R. M., Introducing institutions, (Proc. Logics of Programming Workshop. Proc. Logics of Programming Workshop, Carnegie-Mellon. Proc. Logics of Programming Workshop. Proc. Logics of Programming Workshop, Carnegie-Mellon, Lecture Notes in Computer Science, Vol. 164 (1984), Springer: Springer Berlin), 221-256 · Zbl 1288.03001 [17] Goguen, J. A.; Burstall, R. M., Institutions: abstract model theory for specification and programming, J. ACM, 39, 95-146 (1992) · Zbl 0799.68134 [18] Goguen, J. A.; Meseguer, J., Models and equality for logical programming, (Proc. TAPSOFT’87. Proc. TAPSOFT’87, Lecture Notes in Computer Science, Vol. 250 (1987), Springer: Springer Berlin), 1-22, Vol. 2 [19] Jaffar, J.; Lassez, J.-L., Constraint logic programming, (Proc. 1987 ACM Conf. on Principles of Programming Languages. Proc. 1987 ACM Conf. on Principles of Programming Languages, Munich (1987)), 111-119 [20] Lloyd, J. W., Foundations of Logic Programming (1987), Springer: Springer Berlin · Zbl 0547.68005 [21] Miller, D., A logical analysis of modules in logic programming, J. logic programming, 79-108 (1989) · Zbl 0681.68022 [22] Monteiro, L.; Porto, A., A language for contextual logic programming, (Logic Programming Languages. Constraints, Functions, and Object (1993), MIT Press: MIT Press Cambridge, MA) · Zbl 0832.68015 [24] Sannella, D. T.; Wallen, L. A., A calculus for the construction of modular Prolog programs, (Proc. 1987 IEEE Symp. on Logic Programming (1987)), 368-378 · Zbl 0754.68035 [25] Stuckey, P. J., Constructive negation for constraint logic programming, (Proc. 6th IEEE Symp. on Logic in Computer Science (1991)) · Zbl 0827.68022 [26] Wirsing, M., Algebraic Specification, (Handbook of Theoretical Computer Science, Vol 2: Formal Models and Semantics (1990), Elsevier: Elsevier Amsterdam), 675-788 · Zbl 0900.68309 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.