Hostname: page-component-745bb68f8f-5r2nc Total loading time: 0 Render date: 2025-02-03T21:50:30.105Z Has data issue: false hasContentIssue false
  • English
  • Français

Recurrence with affine level mappings is P-time decidable for CLP

Published online by Cambridge University Press:  01 January 2008

FRED MESNARD  and
ALEXANDER SEREBRENIK
FRED MESNARD
Affiliation:
IREMIA, Université de la Réunion, France (email: [email protected])
ALEXANDER SEREBRENIK
Affiliation:
Laboratory for Quality Software (LaQuSo), T.U. Eindhoven, The Netherlands (email: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we introduce a class of constraint logic programs such that their termination can be proved by using affine level mappings. We show that membership to this class is decidable in polynomial time.

Keywords

constraint logic programmingterminationdecidability
Type
Technical Note
Information
Theory and Practice of Logic Programming , Volume 8 , Issue 1 , January 2008 , pp. 111 - 119
Copyright
Copyright © Cambridge University Press 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Afrati, F. N., Cosmadakis, S. S. and Foustoucos, E. 2005. Datalog programs and their persistency numbers. ACM Transactions on Computational Logic (TOCL) 6 (3), 481–518.CrossRefGoogle Scholar
Basu, S., Pollack, R. and Roy, M.-F. 1996. On the combinatorial and algebraic complexity of quantifier elimination. Journal of the ACM 43 (6), 1002–1045.CrossRefGoogle Scholar
Bezem, M. 1993. Strong termination of logic programs. Journal of Logic Programming 15 (1&2), 79–97.CrossRefGoogle Scholar
Collins, G. E. 1975. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. In Second GI Conference on Automata Theory and Formal Languages. Lecture Notes in Computer Science, Vol. 33. Springer, 134–183.Google Scholar
Cousot, P. 2005. Proving program invariance and termination by parametric abstraction, lagrangian relaxation and semidefinite programming. In Verification, Model Checking, and Abstract Interpretation, 6th International Conference, VMCAI, Paris, France, January 17–19, 2005, Proceedings, Cousot, R., Ed. Lecture Notes in Computer Science, Vol. 3385. Springer, 1–24.Google Scholar
Dantzig, G. B. 1951. Maximization of a linear function of variables subject to linear inequalities. In Activity Analysis of Production and Allocation – Proceedings of a Conference, Koopmans, T., Ed. Cowles Commission Monograph, Vol. 13. Wiley, New York, 339–347.Google Scholar
Devienne, P., Lebègue, P. and Routier, J.-C. P. 1993. Halting problem of one binary horn clause is undecidable. In STACS 93, 10th Annual Symposium on Theoretical Aspects of Computer Science, Würzburg, Germany, February 25–27, 1993, Proceedings., Enjalbert, P., Finkel, A. and Wagner, K. W., Eds. Lecture Notes in Computer Science, Vol. 665. Springer, 48–57.Google Scholar
Holzbaur, C. 1995. OFAI clp(Q,R) Manual. Tech. Rep. TR-95-09, Austrian Research Institute for Artificial Intelligence (ÖFAI), Schottengasse 3, A-1010 Vienna, Austria.Google Scholar
Jaffar, J. and Maher, M. J. 1994. Constraint logic programming: A survey. Journal of Logic Programming 19/20, 503–582.CrossRefGoogle Scholar
Jaffar, J., Maher, M. J., Marriott, K. and Stuckey, P. J. 1998. The semantics of constraint logic programs. Journal of Logic Programming 37 (1–3), 1–46.CrossRefGoogle Scholar
Khachiyan, L. 1979. A polynomial algorithm in linear programming. Soviet Mathematics–-Doklady 20, 191–194.Google Scholar
Marcinkowski, J. 1996. DATALOG SIRUPs uniform boundedness is undecidable. In Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science. 13–24.Google Scholar
Marriott, K. and Stuckey, P. J. 1998. Programming With Constraints: An Introduction. The MIT Press.CrossRefGoogle Scholar
Pheidas, T. 2000. An effort to prove that the existential theory of is undecidable. In Hilbert's Tenth Problem: Relations with Arithmetic and Algebraic Geometry, Denef, J., Lipshitz, L., Pheidas, T. and Geel, J. V., Eds. Contemporary Mathematics 270, 237–252. American Mathematic Society, 2000. MR 2001m:03085.Google Scholar
Podelski, A. and Rybalchenko, A. 2004. A complete method for the synthesis of linear ranking functions. In Verification, Model Checking, and Abstract Interpretation, 5th International Conference, Venice, January 11–13, 2004, Proceedings, Steffen, B. and Levi, G., Eds. Lecture Notes in Computer Science, Vol. 2937. Springer, 239–251.Google Scholar
Renegar, J. 1992. On the computational complexity and geometry of the first-order theory of the reals. Journal of Symbolic Computation 13 (3), 255–352.CrossRefGoogle Scholar
Schrijver, A. 1986. Theory of Linear and Integer Programming. Wiley.Google Scholar
Serebrenik, A. and Mesnard, F. 2004. On termination of binary CLP programs. In Logic Based Program Synthesis and Transformation, 14th International Symposium, LOPSTR, Verona, Italy, August 26–28, 2004, Revised Selected Papers, Etalle, S., Ed. Lecture Notes in Computer Science, Vol. 3573. Springer, 231–244.Google Scholar
SICS. 2005. SICStus User Manual. Version 3.12.3. Swedish Institute of Computer Science.Google Scholar
Sohn, K. and Van Gelder, A. 1991. Termination detection in logic programs using argument sizes. In Proceedings of the Tenth ACM SIGACT-SIGART-SIGMOD Symposium on Principles of Database Systems. ACM Press, 216–226.Google Scholar
Tarski, A. 1931. Sur les ensembles définissables de nombres réels. Fundamenta Mathematicae 17, 210–239.CrossRefGoogle Scholar
Tarski, A. 1951. A Decision Method for Elementary Algebra and Geometry, 2nd ed.University of California Press.CrossRefGoogle Scholar
Tiwari, A. 2004. Termination of linear programs. In Computer-Aided Verification, CAV, Alur, R. and Peled, D., Eds. Lecture Notes on Computer Science, Vol. 3114. Springer, 70–82.CrossRefGoogle Scholar