×

zbMATH — the first resource for mathematics

A necessary condition for constructive negation in constraint logic programming. (English) Zbl 1339.68035
Summary: P. J. Stuckey [Inf. Comput. 118, No. 1, 12–33 (1995; Zbl 0827.68022)] has presented a sound and complete procedure for Constructive Negation in Constraint Logic Programming, together with a sufficient condition, called admissible closure, which guarantees an effective implementation. In this paper we analyze this condition and relate it to the decidability of the underlying constraint structure. We prove that the admissible closure condition is also necessary to guarantee the existence of an effective implementation of Constructive Negation.

MSC:
68N17 Logic programming
68T15 Theorem proving (deduction, resolution, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Apt, K.R.; Bol, R., Logic programming and negation: A survey, J. logic programming, Vol. 19-20, 9-71, (1994) · Zbl 0942.68518
[2] Barbuti, R.; Mancarella, P.; Pedreschi, D.; Turini, F., A transformation approach to negation in logic programming, J. logic programming, Vol. 8, 201-228, (1990) · Zbl 0796.68056
[3] Chan, D., Constructive negation based on the completed database, (), 111-125
[4] Dovier, A.; Omodeo, E.G.; Pontelli, E.; Rossi, G., {log}: A language for programming in logic with finite sets, J. logic programming, Vol. 28, 1, 1-44, (1996) · Zbl 0874.68056
[5] Dovier, A.; Policriti, A.; Rossi, G., A uniform axiomatic view of lists, multisets and sets, and the relevant unification algorithms, Fund. inform., Vol. 36, 2/3, 201-234, (1998) · Zbl 0930.68042
[6] Drabent, W., What is failure? an approach to constructive negation, Acta inform., Vol. 32, 1, 27-29, (1995) · Zbl 0815.68036
[7] Enderton, H.B., A mathematical introduction to logic, (1973), Academic Press New York, 2nd printing
[8] Fages, F., Constructive negation by pruning, J. logic programming, Vol. 32, 2, 85-118, (1997) · Zbl 0882.68034
[9] Jaffar, J.; Maher, M.J., Constraint logic programming: A survey, J. logic programming, Vol. 19-20, 503-581, (1994)
[10] Jaffar, J.; Maher, M.J.; Marriott, K.; Stuckey, P.J., The semantics of constraint logic programs, J. logic programming, Vol. 37, 1-46, (1998) · Zbl 0920.68068
[11] Lloyd, J.W.; Topor, R.W., Making prolog more expressive, J. logic programming, Vol. 1, 3, 225-240, (1984) · Zbl 0584.68022
[12] Maher, M.J., Complete axiomatizations of the algebras of finite, rational and infinite trees, (), 349-357
[13] Przymusinski, T.C., On constructive negation in logic programming, () · Zbl 0726.68067
[14] Shepherdson, J.C., Negation in logic programming, (), 19-88 · Zbl 0718.68020
[15] Stuckey, P.J., Negation and constraint logic programming, Inform. and comput., Vol. 1, 12-33, (1995) · Zbl 0827.68022
[16] Vaught, R.L., On a theorem of cobham concerning undecidable theories, (), 14-25 · Zbl 0178.32303
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.