zbMATH — the first resource for mathematics

Institutions for logic programming. (English) Zbl 0901.68027
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.

MSC:
 68N17 Logic programming
Keywords:
Horn clause logic
Full Text:
References:
 [1] Apt, K.R., Logic programming, (), Ch. 10 · Zbl 1023.03018 [2] Barr, M.; Wells, C., Category theory for computing science, (1990), 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, (), 570-580 · Zbl 0868.68018 [4] Burstall, R.M.; Goguen, J.A., The semantics of clear, a specification language, (), 292-332 · Zbl 0456.68024 [5] Chan, D., Constructive negation based on the completed database, (), 111-125 [6] H. Ehrig, M. Baldamus, F. Cornelius and F. Orejas, Theory of algebraic module specifications including behavioural semantics and constraints, in: Proc. AMAST’91, Lecture Notes in Computer Science (Springer, Berlin, to appear). · Zbl 0923.68089 [7] Ehrig, H.; Baldamus, M.; Orejas, F., New concepts for amalgamation and extension in the framework of specification logics, () [8] Ehrig, H.; Mahr, B., Fundamentals of algebraic specification 1, (1985), Springer Berlin · Zbl 0557.68013 [9] Ehrig, H.; Mahr, B., Fundamentals of algebraic specification 2, (1989), Springer Berlin · Zbl 0557.68013 [10] Ehrig, H.; Orejas, F.; Cornelius, F.; Baldamus, M., Abstract and behaviour module specifications, () · Zbl 0923.68089 [11] Ehrig, H.; Pepper, P.; Orejas, F., On recent trends in algebraic specification, (), 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, (), 1-19 · Zbl 0769.68013 [14] Gaifman, H.; Shapiro, E., Fully abstract compositional semantics for logics programs, (), 134-142 [15] Gaifman, H.; Shapiro, E., Proof theory and semantics of logic programs, (), 50-62 [16] Goguen, J.A.; Burstall, R.M., Introducing institutions, (), 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, (), 1-22, Vol. 2 [19] Jaffar, J.; Lassez, J.-L., Constraint logic programming, (), 111-119 [20] Lloyd, J.W., Foundations of logic programming, (1987), 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, () · Zbl 0832.68015 [23] F. Orejas, E. Pino and H. Ehrig, Algebraic methods in the compositional analysis of logic programs (invited paper), in: I. Privara, B. Rovan and P. Ruzicka, eds., Mathematical Foundations of Computer Science 94 Lecture Notes in Computer Science, Vol. 841 (Springer, Berlin) 112-126. [24] Sannella, D.T.; Wallen, L.A., A calculus for the construction of modular prolog programs, (), 368-378 · Zbl 0754.68035 [25] Stuckey, P.J., Constructive negation for constraint logic programming, () · Zbl 0827.68022 [26] Wirsing, M., Algebraic specification, (), 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. 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.