×

zbMATH — the first resource for mathematics

A functorial framework for constraint normal logic programming. (English) Zbl 1147.68013
Summary: The semantic constructions and results for definite programs do not extend when dealing with negation. The main problem is related to a well-known problem in the area of algebraic specification: if we fix a constraint domain as a given model, its free extension by means of a set of Horn clauses defining a set of new predicates is semicomputable. However, if the language of the extension is richer than Horn clauses its free extension (if it exists) is not necessarily semicomputable. In this paper we present a framework that allows us to deal with these problems in a novel way. This framework is based on two main ideas: a reformulation of the notion of constraint domain and a functorial presentation of our semantics. In particular, the semantics of a logic program \(P\) is defined in terms of three functors \(({\mathcal {OP}}_{P} ,{\mathcal {ALG}}_{P} ,{\mathcal {LOG}}_{P})\) that apply to constraint domains and provide the operational, the least fixpoint and the logical semantics of \(P\), respectively. To be more concrete, the idea is that the application of \({\mathcal {OP}}_{P}\) to a specific constraint solver provides the operational semantics of \(P\) that uses this solver; the application of \({\mathcal {ALG}}_{P}\) to a specific domain provides the least fixpoint of \(P\) over this domain; and the application of \({\mathcal {LOG}}_{P}\) to a theory of constraints provides the logic theory associated to \(P\). In this context, we prove that these three functors are in some sense equivalent.
MSC:
68N17 Logic programming
68Q55 Semantics in the theory of computing
18C50 Categorical semantics of formal languages
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Álvez, J., Lucio, P., Orejas, F.: Constructive negation by bottom-up computation of literal answers. In: Proceedings of the 2004 ACM Symposium on Applied Computing, pp. 1468–1475 (2004)
[2] Bergstra, J.A., Broy, M., Tucker, J.V., Wirsing, M.: On the power of algebraic specifications. In: Gruska, J., Chytil, M. (eds.) Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31–September 4, 1981, Proceedings MFCS. Lecture Notes in Computer Science, vol. 118, pp. 193–204. Springer (1981) · Zbl 0462.68001
[3] Carnielli, W.A.: Sistematization of finite many-valued logics through the method of tableaux. J. Symbolic Logic 52(2), 473–493 (1987) · Zbl 0633.03008 · doi:10.2307/2274395
[4] Clark, K.L.: Negation as failure. In: Gallaire, H., Minker, J. (eds.) Logic and Databases, pp. 293–322. Plenum Press, New York (1978)
[5] Drabent, W.: What is a failure? An approach to constructive negation. Acta Inform. 32, 27–59 (1995) · Zbl 0815.68036 · doi:10.1007/BF01185404
[6] Fages, F.: Constructive negation by pruning. J. Logic Programming 32, 85–118 (1997) · Zbl 0882.68034 · doi:10.1016/S0743-1066(96)00092-1
[7] Fitting, M.: A Kripke–Kleene semantics for logic programs. J. Logic Programming 4, 295–312 (1985) · Zbl 0589.68011 · doi:10.1016/S0743-1066(85)80005-4
[8] Goguen, J., Meseguer, J.: Initiality, induction and computability. In: Nivat, M., Reynolds, J. (eds.) Algebraic Methods in Semantics. Cambridge Univ. Press, pp. 459–540 (1985) · Zbl 0571.68004
[9] Jaffar, J., Lassez, J.-L.: Constraint logic programming. In: POPL, pp. 111–119 (1987)
[10] Jaffar, J., Maher, M.: Constraint logic programming: a survey. J. Logic Programming 19/20, 503–581 (1994) · Zbl 00639141 · doi:10.1016/0743-1066(94)90033-7
[11] Jaffar, J., Maher, M., Marriot, K., Stukey, P.: The semantics of constraint logic programs. J. Logic Programming 37(1), 1–46 (1998) · Zbl 0920.68068 · doi:10.1016/S0743-1066(98)10002-X
[12] Kleene, S.C.: Introduction to Metamathematics. Van Nostrand (1952) · Zbl 0047.00703
[13] Kunen, K.: Signed data dependencies in logic programs. J. Logic Programming 7, 231–245 (1989) · doi:10.1016/0743-1066(89)90022-8
[14] Lloyd, J.W.: Foundations of Logic Programming. Springer-Verlag, 2nd edn. (1987) · Zbl 0668.68004
[15] 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 · doi:10.1016/S0743-1066(98)10039-0
[16] Lucio, P., Orejas, F., Pasarella, E., Pino, E.: A functorial framework for constraint normal logic programming. In: Futatsugi, K., Jouannaud, J.-P., Meseguer, J. (eds.) Algebra, Meaning, and Computation, Essays, Dedicated to Joseph A. Goguen on the Occasion of His 65th Birthday. Lecture Notes in Computer Science, vol. 4060, pp. 555–577. Springer-Verlag (2006) · Zbl 1132.68324
[17] Pasarella, E., Pino, E., Orejas, F.: Constructive negation without subsidiary trees. In: 9th International Workshop on Functional and Logic Programming (WFLP’00), Benicàssim, Spain (2000)
[18] Przymusinski, T.: On the declarative semantics of deductive databases and logic programs. In: Minker, J. (ed.) Foundations of Deductive Databases and Logic Progamming, pp. 193–216. Morgan Kaufmann (1988) · Zbl 0726.68067
[19] Shepherdson, J.C.: Language and equality theory in logic programming. Technical report PM-91-02, University of Bristol (1991) · Zbl 0764.68156
[20] Stuckey, P.J.: Negation and constraint logic programmming. Inform. and Comput. 118, 12–23 (1995) · Zbl 0827.68022 · doi:10.1006/inco.1995.1048
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.