Search
1991 Volume 6
Article Contents
RESEARCH ARTICLE   Open Access    

Constraint logic programming

More Information
  • Abstract: Constraint logic programming (CLP) is a generalization of logic programming (LP) where unification, the basic operation of LP languages, is replaced by constraint handling in a constraint system. The resulting languages combine the advantages of LP (declarative semantics, nondeterminism, relational form) with the efficiency of constraint-solving algorithms. For some classes of combinatorial search problems, they shorten the development time significantly while preserving most of the efficiency of imperative languages.This paper surveys this new class of programming languages from their underlying theory, to their constraint systems, and to their applications to combinatorial problems.
  • 加载中
  • Aiba A, Sakai K, Sato Y, Hawley DJ and Hasegawa R, 1988. “Constraint logic programming CAL” In: Proceedings of the International Conference on Fifth Generation Computer SystemsTokyo, Japan,December.

    Google Scholar

    Ait-kaci H and Nasr R, 1986. “LOGIN: a logic programming language with built-in inheritance” Journal of Logic Programming3(3) 185–215, October.

    Google Scholar

    Ait-kaci H and Podelski A, 1990. “Is there a meaning to LIFE” (submitted for publication).

    Google Scholar

    Berthier F, 1988. “Using CHIP to support decision making” In: Actes du Seminaire 1988–Programmation en Logique Tregastel, France, May.

    Google Scholar

    Borning A, Maher M, Martingale A and Wilson M, 1989. “Constraint hierarchies and logic programming” In: Sixth International Conference on Logic ProgrammingLisbon, Portugal,June.

    Google Scholar

    Bryant RE, 1986. “Graph based algorithms for Boolean function manipulation” IEEE Transactions on Computers35(8) 677–691.

    Google Scholar

    Brzozowski JA and Yoeli M, 1985. Combinatorial Static CMOS Networks. Technical Report CS-85–42, University of Waterloo.

    Google Scholar

    Buchberger B, 1985. Groebner Bases: An Algorithmic Method in Polynomial Ideal Theory, Reidel Publishing Co.

    Google Scholar

    Buttner W and Simonis H, 1987. “Embedding Boolean expressions into logic programming” Journal of Symbolic Computation4191–205, October.

    Google Scholar

    Clark KL and McCabe F, 1979. “The control facilities of IC-PROLOG” In: Mitchie D (ed.), Expert Systems in the Micro Electronic AgeEdinburgh University Press.

    Google Scholar

    Clocksin WF, 1987. “Logic programming and digital circuit analysis” J. Logic Programming4(1) 59–82.

    Google Scholar

    Cohen J, 1990. “Constraint logic programming languages” Commun. ACM28(4).

    Google Scholar

    Colmerauer A, Kanoui H, Pasero R and Roussel P, 1973. Un système de communication homme-machine en français. Rapport de recherche, Groupe Intelligence Artificielle, Université d'Aix-Marseille II.

    Google Scholar

    Colmerauer A, Kanoui H and Van Caneghem M, 1983. “Prolog, bases theoriques et developpements actuels” Techniques et Sciences Informatiques2(4) 271–311.

    Google Scholar

    Colmerauer A, 1987. “Opening the Prolog-III universe” BYTE Magazine12(9).

    Google Scholar

    Colmerauer A, 1990. “An introduction to Prolog III” Commun. ACM28(4) 412–418.

    Google Scholar

    Cox J, McAloon K and Tretkoff C, 1990. “Computational complexity and constraint logic programming languages” In: Proceedings of the North-American Conference on Logic Programming (NACLP-90),Austin, TX,October.

    Google Scholar

    Dantzig GB, Orden A and Wolfe P, 1955. “The generalized simplex method for minimizing a linear form under linear inequality constraints” Pacific J. Math.5(2) 183–195.

    Google Scholar

    Davis M and Putman H, 1960. “A computation procedure for quantification theory” J. ACM7201–215.

    Google Scholar

    Davis R, 1984. “Diagnostic reasoning based on structure and behavior” Artificial Intelligence24347–410.

    Google Scholar

    Deville Y and Van Hentenryck P, 1991. “An efficient arc consistency algorithm for a class of CSP problems” In: International Joint Conference on Artificial IntelligenceSydney, Australia,August.

    Google Scholar

    Dincbas M, Simonis H and Van Hentenryck P, 1988a. “Solving a cutting-stock problem in constraint logic programming” In: Fifth International Conference on Logic ProgrammingSeattle, W A,August.

    Google Scholar

    Dincbas M, Simonis H and Van Hentenryck P, 1988b. “Solving large scheduling problems in logic programming” In: EURO-TIMS Joint International Conference on Operations Research and Management ScienceParis, France,July.

    Google Scholar

    Dincbas M, Simonis H and Van Hentenryck P, 1988c. “Solving the car sequencing problem in constraint logic programming” In: European Conference on Artificial Intelligence (ECAI-88)Munich, Germany,August.

    Google Scholar

    Dincbas M, Simonis H and Van Hentenryck P, 1990. “Solving large combinatorial problems in logic programming”: J. Logic Programming8(1–2) 75–93.

    Google Scholar

    Dincbas M, Van Hentenryck P, Simonis H, Aggoun A, Graf T and Berthier F, 1988. “The constraint logic programming language CHIP” in: Proceedings of the International Conference on Fifth Generation Computer SystemsTokyo, Japan,December.

    Google Scholar

    Fikes RE, 1968. A Heuristic Program for Solving Problems Stated as Non-deterministic Procedures, PhD thesis, Computer Science Department, Carnegie-Mellon University, Pittsburgh.

    Google Scholar

    Gallaire H, 1985. “Logic programming: further developments” In: IEEE Symposium on Logic Programming, pp 88–99, Boston, MA, July.

    Google Scholar

    Gallaire H and Lasserre C, 1982. Metalevel Control for Logic ProgramsAcademic Press.

    Google Scholar

    Gorlick MM, Kesselman CVF, Marotta DA and Parker DS, 1990. “Mockingbird: a logical methodology for testing” J. Logic Programming8(1–2) 95–119.

    Google Scholar

    Graf T, 1987. Extending Constraint Handling in Logic Programming to Rational Arithmetic. Internal Report, ECRC, Munich, Germany, 09.

    Google Scholar

    Graf T, 1989. Raisonner sur les contraintes en programmation logique, PhD thesis, Université de Nice, France.

    Google Scholar

    Graf T, Van Hentenryck P, Pradelles C and Zimmer L, 1989. “Simulation of hybrid circuits in constraint logic programming” In: International Joint Conference on Artificial IntelligenceDetroit, MI,August.

    Google Scholar

    Graf T, Van Hentenryck P, Pradelles C and Zimmer L, 1990. “Simulation of hybrid circuits in constraint logic programming” Computers and Mathematics with Applications20(9/10) 45–56.

    Google Scholar

    Haridi S, 1990. “A logic programming language based on the Ando¡rra model” New Generation Computation (to appear).

    Google Scholar

    Heintze NC, Michaylov S and Stuckey PJ, 1987. “CLP(ℜ) and some electrical engineering problems” In: Fourth International Conference on Logic ProgrammingMelbourne,Australia,May.

    Google Scholar

    Heintze N, Michaylov S, Stuckey P and Yap R, 1989. “On meta-programming in CLP(ℜ)” In: Proceedings of the North-American Conference on Logic Programming (NACLP-89), pp 52–68, Cleveland, OH,October.

    Google Scholar

    Imbert JL, 1990, “About redundant inequalities generated by Fourier's algorithm” In: AIMSA '90, Fourth International Conference on Artificial Intelligence: Methodology, Systems, ApplicationsAlbena-Varna,Bulgaria,September.

    Google Scholar

    Imbert JL and Van Hentenryck P, 1991. Efficient Handling of Disequations in CLP over Linear Rational Arithmetics. Technical Report CS-91–23, CS Department, Brown University.

    Google Scholar

    Jaffar J and Lassez J-L, 1987. “Constraint logic programming” In: POPL–87Munich, Germany, 01.

    Google Scholar

    Jaffar J and Michaylov S, 1987. “Methodology and implementation of a CLP system” In: Fourth International Conference on Logic ProgrammingMelbourne,Australia,May.

    Google Scholar

    Jaffar J, Michaylov S, Stuckey PJ and Yap R, 1990. “The CLP(ℜ) Language and System. Research report”, IBM.

    Google Scholar

    Jorgensen N and Marriot K, 1990. “Useful compile-time optimizations for CLP(ℜ)”, (draft).

    Google Scholar

    Kanellakis PC, Kuper GM and Revesz PZ, 1990. “Constraint query languages” In: PODS-90 Nashville, TE.

    Google Scholar

    Karmarkar N, 1984. “A new polynomial-time algorithm for linear programming” Combinatorica4(4) 373–395.

    Google Scholar

    Khachian LG, 1979. “A polynomial algorithm in linear programming” Soviet Math. Dokl.20(1) 191–194.

    Google Scholar

    Kowalski R, 1974. “Predicate logic as programming language” In: Proceedings of the IFIP Congress 74, pp 569–574, North-Holland.

    Google Scholar

    Lassez J-L, Huynh T and McAloon K, 1989. “Simplification and elimination of redundant arithmetic constraints” In: Proceedings of the North-American Conference on Logic Programming (NACLP-89)Cleveland, OH,October.

    Google Scholar

    Lassez J-L and McAloon K, 1988. “Applications of a canonical form for generalized linear constraints” In: Proceedings of the International Conference on Fifth Generation Computer SystemsTokyo, Japan,December.

    Google Scholar

    Lassez C, McAloon K and Yap R, 1987. “Constraint logic programming and option trading” IEEE Expert2(3) 42–50.

    Google Scholar

    Lauriere J-L, 1978. “A language and a program for stating and solving combinatorial problems” Artificial Intelligence10(1) 29–127.

    Google Scholar

    Lim P and Stuckey P, 1990. “Meta programming as constraint programming” In: Proceedings of the North-American Conference on Logic Programming (NACLP-90)Austin, TX,October.

    Google Scholar

    Mackworth AK, 1977. “Consistency in networks of relations” AI Journal8(1) 99–118.

    Google Scholar

    Maher MJ, 1987. “Logic semantics for a class of committed-choice programs” In: Fourth International Conference on Logic Programming, pp 858–876, Melbourne,Australia,May.

    Google Scholar

    Maher M and Stuckey P, 1989. “Expanding query power in constraint logic programming languages” In: Proceedings of the North-American Conference on Logic Programming (NACLP-89)Cleveland, OH,October.

    Google Scholar

    Marriot K and Sondergaard H, 1990. “Analysis of constraint logic programs”: In: Proceedings of the North-American Conference on Logic Programming (NACLP-90)Austin, TX,October.

    Google Scholar

    Martin U and Nipkow T, 1986. “Unification in Boolean rings” In: Proceedings of the 8th Conference on Automated Deduction, pp 506–513, Oxford, UK,July.

    Google Scholar

    Mohr R and Henderson TC, 1986. “Arc and path consistency revisited” Artificial Intelligence28225–233.

    Google Scholar

    Montanari U and Rossi F, 1986. “An efficient algorithm for the solution of hierarchical networks of constraints”: In: Workshop on Graph Grammars and their Applications in Computer Science Warrenton, DC, December.

    Google Scholar

    Naish L, 1985. Negation and Control in Prolog, PhD thesis, University of Melbourne, Australia.

    Google Scholar

    Older WandVellino A, 1990. “Extending Prolog with constraint arithmetics on real intervals” In: Canadian Conference on Computer & Electrical EngineeringOttawa.

    Google Scholar

    Parker DS and Muntz RR, “A Theory of Directed Logic Programs and Streams” In: Fifth International Conference on Logic Programming,Seattle, WA,August.

    Google Scholar

    Parker RG and Rardin RL, 1988. Discrete OptimizationAcademic Press.

    Google Scholar

    Parrello BD, 1988. “CAR WARS: the (almost) birth of an expert system” AI Expert3(1) 60–64.

    Google Scholar

    Plotkin GD, 1981. A Structural Approach to Operational Semantics. Technical Report DAIMI FN-19, CS Department, University of Aarhus.

    Google Scholar

    Radeanu S, 1974. Boolean Functions and EquationsNorth-Holland.

    Google Scholar

    Rossi F, 1991. Towards an Ideal Notion of Constraint Programming, PhD Thesis Proposal, Computer Science Department, University of Pisa, Italy.

    Google Scholar

    Saraswat VA, 1989. Concurrent Constraint Programming Languages, PhD thesis, Carnegie-Mellon University.

    Google Scholar

    Saraswat VA, Kahn K and Levy J, 1990. “Janus: a step towards distributed constraint programming” In: Proceedings of the North-American Conference on Logic Programming (NACLP-90)Austin, TX,October.

    Google Scholar

    Saraswat VA and Rinard M, 1990. Concurrent constraint programming” In: Proceedings of Seventeenth ACM Symposium on Principles of Programming LanguagesSan Francisco, CA, 01.

    Google Scholar

    Saraswat VA, Rinard M and Panangaden P, 1991. “Semantic foundations of concurrent constraint programming” In: Proceedings of Ninth ACM Symposium on Principles of Programming LanguagesOrlando, FL, 01.

    Google Scholar

    Shapiro E, 1990. “The family of concurrent logic programming languages” Computing Surveys21(3) 413–510.

    Google Scholar

    Simonis H, 1989. “Test generation using the constraint logic programming language CHIP” In: Sixth International Conference on Logic ProgrammingLisbon,Portugal,June.

    Google Scholar

    Simonis H and Dincbas M, 1987a. “Using an extended Prolog for digital circuit design” In: IEEE International Workshop on AI Applications to CAD Systems for Electronics, pp 165–188, Munich, Germany, 10.

    Google Scholar

    Simonis H and Dincbas M, 1987b. “Using logic programming for fault diagnosis in digital circuits” In: German Workshop on Artificial Intelligence (GWAI-87), pp 139–148, Geseke, Germany, September.

    Google Scholar

    Smith DA and Hickey TJ, 1990. “Partial evaluation of a CLP language” In: Proceedings of the North-American Conference on Logic Programming (NACLP-90)Austin, TX,October.

    Google Scholar

    Stuckey PJ, 1990. “Incremental linear arithmetic constraint solving and detection of implicit equalities” (submitted for publication).

    Google Scholar

    Sussman GJ and Steele GL, 1980. “CONSTRAINTS—A language for expressing almost-hierarchical descriptions” AI Journal14(1).

    Google Scholar

    Van Hentenryck P, 1989a. “A logic language for combinatorial optimization” Annals of Operations Research21247–274.

    Google Scholar

    Van Hentenryck P, 1989b. Constraint Satisfaction in Logic Programming Logic Programming Series, The MIT Press.

    Google Scholar

    Van Hentenryck P, 1989c. “Parallel constraint satisfaction in logic programming: preliminary results of CHIP within PEPSys” In: Sixth International Conference on Logic ProgrammingLisbon,Portugal,June.

    Google Scholar

    Van Hentenryck P, 1990. “Incremental constraint satisfaction in logic programming” In: Seventh International Conference on Logic ProgrammingJerusalem, Israel,June.

    Google Scholar

    Van Hentenryck P and Deville Y, 1990. Operational Semantics of Constraint Logic Programming over Finite Domains. Technical Report CSA-90–23, CS Department, Brown University.

    Google Scholar

    Van Hentenryck P and Deville Y, 1991. “The cardinality operator: a new logical connective and its application to constraint logic programming” In: Eighth International Conference on Logic Programming (ICLP-91)Paris, France,June.

    Google Scholar

    Van Hentenryck P and Graf T, 1990. “Standard forms for rational linear arithmetics in constraint logic programming” In: International Symposium on Artificial Intelligence and MathematicsFort Lauderdale, FL, 01, (also ECRC internal Report IR-LP-2217.)

    Google Scholar

    Voda P, 1988. The Constraint Language Trilogy: Semantics and Computations. Technical report, Complete Logic Systems, North Vancouver, BC, Canada.

    Google Scholar

    Walinsky C, 1989. “CLP(σ*)” In: Sixth International Conference on Logic ProgrammingLisbon, Portugal,June.

    Google Scholar

  • Cite this article

    Pascal Van Hentenryck. 1991. Constraint logic programming. The Knowledge Engineering Review. 6:8 doi: 10.1017/S0269888900005798
    Pascal Van Hentenryck. 1991. Constraint logic programming. The Knowledge Engineering Review. 6:8 doi: 10.1017/S0269888900005798

Article Metrics

Article views(14) PDF downloads(220)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Constraint logic programming

The Knowledge Engineering Review  6 Article number: 10.1017/S0269888900005798  (1991)  |  Cite this article

Abstract: Abstract: Constraint logic programming (CLP) is a generalization of logic programming (LP) where unification, the basic operation of LP languages, is replaced by constraint handling in a constraint system. The resulting languages combine the advantages of LP (declarative semantics, nondeterminism, relational form) with the efficiency of constraint-solving algorithms. For some classes of combinatorial search problems, they shorten the development time significantly while preserving most of the efficiency of imperative languages.This paper surveys this new class of programming languages from their underlying theory, to their constraint systems, and to their applications to combinatorial problems.

    • Copyright © Cambridge University Press 19911991Cambridge University Press
References (87)
  • About this article
    Cite this article
    Pascal Van Hentenryck. 1991. Constraint logic programming. The Knowledge Engineering Review. 6:8 doi: 10.1017/S0269888900005798
    Pascal Van Hentenryck. 1991. Constraint logic programming. The Knowledge Engineering Review. 6:8 doi: 10.1017/S0269888900005798
  • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return