article

Open access

An interval constraint system for lattice domains

Authors:

Antonio J. Fernández,

Patricia M. HillAuthors Info & Claims

ACM Transactions on Programming Languages and Systems (TOPLAS), Volume 26, Issue 1

Pages 1 - 46

https://doi.org/10.1145/963778.963779

Published: 01 January 2004 Publication History

Abstract

We present a generic framework for defining and solving interval constraints on any set of domains (finite or infinite) that are lattices. The approach is based on the use of a single form of constraint similar to that of an indexical used by CLP for finite domains and on a particular generic definition of an interval domain built from an arbitrary lattice. We provide the theoretical foundations for this framework and a schematic procedure for the operational semantics. Examples are provided that illustrate how new (compound) constraint solvers can be constructed from existing solvers using lattice combinators and how different solvers (possibly on distinct domains) can communicate and hence, cooperate in solving a problem. We describe the language clp(L), which is a prototype implementation of this framework and discuss ways in which this implementation may be improved.

References

[1]

Aït-kaci, H. 1999. Warren's Abstract Machine: A Tutorial Reconstruction. The MIT Press, Cambridge, MA.]]

Digital Library

[2]

Allen, J. 1983. Maintaining knowledge about temporal intervals. Commun. ACM 26, 11, 832--843.]]

Digital Library

[3]

Apt, K. 1999. The rough guide to constraint propagation. In 5th International Conference on Principles and Practice of Constraint Programming (CP'99, Alexandria, Virginia), J. Jaffar, Ed. Lecture Notes in Computer Science, vol. 1713. Springer-Verlag, Berlin, Germany, 1--23.]]

Digital Library

[4]

Apt, K. 2000. The role of commutativity in constraint propagation algorithms. ACM Trans. Programm. Lang. Syst. 22, 6, 1002--1036.]]

Digital Library

[5]

Baader, F. and Schulz, K. 1995. On the combination of symbolic constraints, solution domains and constraints solvers. In 1st International Conference on Principles and Practice of Constraint Programming (CP'95, Cassis, France), U. Montanari and F. Rossi, Eds. Lecture Notes in Computer Science, vol. 976. Springer-Verlag, Berlin, Germany, 380--397.]]

Digital Library

[6]

Barth, P. and Bockmayr, A. 1996. Modelling 0-1 problems in CLP(PB). In 2nd International Conference on the Practical Application of Constraint Technology (PACT'96), M. Wallace, Ed. Prolog Management Group, London, U.K., 1--9.]]

[7]

Benhamou, F. 1995. Interval constraint logic programming. In Constraint Programming: Basics and Trends, A. Podelski, Ed. Lecture Notes in Computer Science, vol. 910. Springer-Verlag, Berlin, Germany, 1--21.]]

Digital Library

[8]

Benhamou, F., Goualard, F., Granvilliers, L., and Puget, J.-F. 1999. Revising hull and box consistency. In 16th International Conference on Logic Programming (ICLP'99, Las Cruces, New Mexico,) D. De Schreye, Ed. The MIT Press, Cambridge, MA, 230--244.]]

Digital Library

[9]

Benhamou, F. and Older, W. 1997. Applying interval arithmetic to real, integer and Boolean constraints. J. Logic Programm. 32, 1 (July), 1--24.]]

[10]

Birkhoff, G. 1967. Lattice Theory, 3rd ed. Coloquium Publications, vol. XXV. American Mathematical Society, Providence RI.]]

[11]

Bistarelli, S., Montanari, U., and Rossi, F. 1995. Constraint solving over semirings. In 14th International Joint Conference on Artificial Intelligent (IJCAI'95, Québec, Canada). Morgan Kaufman, San Francisco, CA, 624--630.]]

[12]

Carlsson, M., Ottosson, G., and Carlson, B. 1997. An open-ended finite domain constraint solver. In 9th International Symposium on Programming Languages: Implementations, Logics and Programs (PLILP'97, Southampton, U.K.), U. Montanari and F. Rossi, Eds. Lecture Notes in Computer Science, vol. 1292. Springer-Verlag, Berlin, Germany, 191--206.]]

Digital Library

[13]

Cleary, J. 1987. Logical arithmetic. Fut. Comput. Syst. 2, 2, 125--149.]]

[14]

Codognet, P. and Diaz, D. 1993. Boolean constraint solving using clp(FD). In 1993 International Symposium on Logic Programming (ILPS'93 Vancouver, British Columbia, Canada), D. Miller, Ed. The MIT Press, Cambridge, MA, 525--539.]]

Digital Library

[15]

Codognet, P. and Diaz, D. 1994. clp(B): combining simplicity and efficiency in Boolean constraint solving. In 6th International Symposium on Programming Languages Implementation and Logic Programming (PLILP'94, Madrid, Spain). Lecture Notes in Computer Science, vol. 844. Springer-Verlag, Berlin, Germany, 244--260.]]

Digital Library

[16]

Codognet, P. and Diaz, D. 1996a. Compiling constraints in clp(FD). J. Logic Programm. 27, 3, 185--226.]]

[17]

Codognet, P. and Diaz, D. 1996b. A simple and efficient Boolean solver for constraint logic programming. J. Automat. Reason. 17, 1, 97--129.]]

[18]

Davey, B. and Priestley, H. 1990. Introduction to Lattices and Order. Cambridge University Press, Cambridge, England.]]

[19]

Diaz, D. and Codognet, P. 1993. A minimal extension of the WAM for clp(FD). In 10th International Conference on Logic Programming (ICLP'93, Budapest, Hungary), D. Warren, Ed. The MIT Press, Cambridge, MA, 774--790.]]

Digital Library

[20]

Diaz, D. and Codognet, P. 2001. Design and implementation of the GNU prolog system. J. Funct. Logic Programm. 2001, 6 (Oct.).]]

[21]

Fernández, A. 2000. clp(L) version 0.21, user manual. Available online at http://www.lcc.uma.es/&sim;afdez/generic.]]

[22]

Fernández, A. 2002. A generic, collaborative framework for interval constraint solving. Ph.D. dissertation, E.T.S.I.I., Dpto. Lenguajes y Ciencias de la Computación, University of Málaga, Spain. English version available online at http://www.lcc.uma.es/&sim;afdez/papers.html.]]

[23]

Fernández, A. and Hill, P. 1999a. Interval constraint solving over lattices using chaotic iterations. In ERCIM/COMPULOG Workshop on Constraints, K.Apt, A. Kakas, E. Monfroy, and F. Rossi, Eds. Dept., of Computer Science, University of Cyprus, Paphos, Cyprus. Available online at http://www.cwi.nl/ERCIM/WG/Constraints/Workshops/Workshop4/Program.]]

[24]

Fernández, A. and Hill, P. 1999b. An interval lattice-based constraint solving framework for lattices. In 4th International Symposium on Functional and Logic Programming (FLOPS'99, Tsukuba, Japan), A. Middeldorp and T. Sato, Eds. Lecture Notes in Computer Science, vol. 1722. Springer-Verlag, Berlin, Germany, 194--208.]]

Digital Library

[25]

Fernández, A. and Hill, P. 2000. A comparative study of eight constraint programming languages over the Boolean and finite domains. Constraints 5, 3, 275--301.]]

Digital Library

[26]

Frühwirth, T. 1998. Theory and practice of constraint handling rules. J. Logic Programm. 37, 95--138.]]

[27]

Georget, Y. and Codognet, P. 1998. Compiling semiring-based constraints with clp(FD,S). In 4th International Conference on Principles and Practice of Constraint Programming (CP'98, Pisa, Italy), M. Maher and J.-F. Puget, Eds. Lecture Notes in Computer Science, vol. 1520. Springer-Verlag, Berlin, Germany, 205--219.]]

Digital Library

[28]

Gervet, C. 1997. Interval propagation to reason about sets: Definition and implementation of a practical language. Constraints 1, 3, 191--244.]]

[29]

Goualard, F., Benhamou, F., and Granvilliers, L. 1999. An extension of the WAM for hybrid interval solvers. J. Funct. Logic Programm. 1999, 1 (April), 1--36. Special issue of Workshop on Parallelism and Implementation Technology for (Constraint) Logic Programming Languages.]]

Digital Library

[30]

Hickey, T. 2000. CLIP: a CLP(Intervals) dialect for metalevel constraint solving. In 2nd International Workshop on Practical Aspects of Declarative Languages (PADL'2000, Boston, Massachusetts), E. Pontelli and V. Costa, Eds. Lecture Notes in Computer Science, vol. 1753. Springer-Verlag, Berlin, Germany, 200--214.]]

Digital Library

[31]

Hofstedt, P. 2000. Better communication for tighter cooperation. In 1st International Conference on Computational Logic (CL'2000, London, U.K.), J. W. Lloyd, V. Dahl, U. Furbach, M. Kerber, K. Lau, C. Palamidessi, L. Pereira, Y. Sagiv, and P. J. Stuckey, Eds. Lecture Notes in Computer Science, vol. 1861. Springer-Verlag, Berlin, Germany, 342--357.]]

Digital Library

[32]

If/Prolog. 1994. IF/Prolog V5.0A, Constraints Package. Siemens Nixdorf Informationssysteme AG, Munich, Germany.]]

[33]

ISO/IEC. 1995. ISO/IEC 13211-1: 1995 Information Technology---Programming Languages---Prolog---Part 1: General Core. International Standard Organization, Geneva, Switzerland.]]

[34]

Jaffar, J., Michaylov, S., Stuckey, P., and Yap, R. 1992. The CLP(R) language and system. ACM Trans. Programm. Lang. Syst. 14, 3, 339--395.]]

Digital Library

[35]

Le Provost, T. and Wallace, M. 1993. Generalized constraint propagation over the CLP scheme. J. Logic Programm. 16, 3 (Aug.), 319--359.]]

[36]

Lee, J. and van Emden, M. 1993. Interval computation as deduction in CHIP. Journal Logic Programm. (Special Issue on Constraint Logic Programming) 16, 3-4, 255--276.]]

[37]

Moore, R. 1966. Interval Analysis. Prentice Hall, Englewood Cliffs, NJ.]]

[38]

N'Dong, S. 1997. Prolog IV ou la programmation par contraintes selon PrologIA. In Sixièmes Journées Francophones de Programmation Logique et Programmation par Contraintes (JFPLC'97). Edition HERMES, Orléans, France, 235--238.]]

[39]

Older, W. 1989. Interval arithmetic specification. Tech. Rep. Bell-Northern, Research Computing Research Laboratory, Ottawa, Ontario, Canada.]]

[40]

Older, W. and Vellino, A. 1993. Constraint arithmetic on real intervals. In Constraint Logic Programming: Selected Research, F. Benhamou and A. Colmesauer, Eds. The MIT Press, Cambridge, MA, 175--195.]]

Digital Library

[41]

Refalo, P. and Van Hentenryck, P. 1996. CLP(Rlin) revised. In Joint International Conference and Symposium on Logic Programming (JICSLP'96, Bonn, Germany), M. Maher, Ed. The MIT Press, Cambridge, MA, 22--36.]]

[42]

Schiex, T., Fargier, H., and Verfaillie, G. 1995. Valued constraint satisfaction problems: Hard and easy problems. In 14th International Joint Conference on Artificial Intelligent (IJCAI'95, Québec, Canada). Morgan Kaufman, San Francisco, CA, 631--637.]]

[43]

Sicstus Manual. 1994. SICStus Prolog User's Manual, Release 3&num;5. The Intelligent Systems Laboratory, Swedish Institute of Computer Science. Web site: http://www.sics.se.]]

[44]

Sidebottom, G. and Havens, W. 1992. Hierarchical arc consistency for disjoint real intervals in constraint logic programming. Computat. Intell. 8, 4, 601--623.]]

[45]

Slavík, V. 1986. A note on the lattice of intervals of a lattice. Algebra Universalis 23, 1, 22--23.]]

[46]

Van Hentenryck, P., Saraswat, V., and Deville, Y. 1998. Design, implementation and evaluation of the constraint language cc(FD). J. Logic Programm. 37, 1--3 (Oct.), 139--164.]]

[47]

Walinsky, C. 1989. CLP(Σ*): Constraint logic programming with regular sets. In 6th International Conference on Logic Programming (ICLP'89, Lisbon, Portugal), G. Levi and M. Martelli, Eds. The MIT Press, Cambridge, MA, 181--196.]]

Cited By

TALBOT PMONFROY ÉTRUCHET C(2020)Modular Constraint Solver Cooperation via Abstract InterpretationTheory and Practice of Logic Programming10.1017/S147106842000016220:6(848-863)Online publication date: 22-Sep-2020
https://doi.org/10.1017/S1471068420000162
Talbot PKomendantskaya E(2019)Spacetime ProgrammingProceedings of the 21st International Symposium on Principles and Practice of Declarative Programming10.1145/3354166.3354183(1-16)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1145/3354166.3354183
Talbot PCachera DMonfroy ETruchet C(2019)Combining Constraint Languages via Abstract Interpretation2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI.2019.00016(50-58)Online publication date: Nov-2019
https://doi.org/10.1109/ICTAI.2019.00016
Show More Cited By

Index Terms

An interval constraint system for lattice domains
1. Software and its engineering
  1. Software notations and tools
    1. General programming languages
      1. Language features
        Constraints
      2. Language types
        Constraint and logic languages
2. Theory of computation
  1. Semantics and reasoning
    1. Program semantics
      1. Operational semantics

Recommendations

A Generic, Collaborative Framework for Interval Constraint Solving: Thesis

The paper abstracts the contents of a PhD dissertation entitled A Generic, Collaborative Framework for Interval Constraint Solving which has been recently defended. This thesis presents a generic framework for defining and solving interval constraints ...
Thesis: a generic, collaborative framework for interval constraint solving

The paper abstracts the contents of a PhD dissertation entitled A Generic, Collaborative Framework for Interval Constraint Solving which has been recently defended. This thesis presents a generic framework for defining and solving interval constraints ...
Lattice-valued finite state machines and lattice-valued transformation semigroups

This paper provides a generalization of known results about fuzzy finite state machines, fuzzy transformation semigroups and their relationship by broading the truth values domain from the interval [0,1] to a complete lattice endowed with a t-norm and a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Programming Languages and Systems

ACM Transactions on Programming Languages and Systems Volume 26, Issue 1

January 2004

220 pages

ISSN:0164-0925

EISSN:1558-4593

DOI:10.1145/963778

Issue’s Table of Contents

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2004

Published in TOPLAS Volume 26, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
875
Total Downloads

Downloads (Last 12 months)51
Downloads (Last 6 weeks)5

Reflects downloads up to 17 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

TALBOT PMONFROY ÉTRUCHET C(2020)Modular Constraint Solver Cooperation via Abstract InterpretationTheory and Practice of Logic Programming10.1017/S147106842000016220:6(848-863)Online publication date: 22-Sep-2020
https://doi.org/10.1017/S1471068420000162
Talbot PKomendantskaya E(2019)Spacetime ProgrammingProceedings of the 21st International Symposium on Principles and Practice of Declarative Programming10.1145/3354166.3354183(1-16)Online publication date: 7-Oct-2019
https://dl.acm.org/doi/10.1145/3354166.3354183
Talbot PCachera DMonfroy ETruchet C(2019)Combining Constraint Languages via Abstract Interpretation2019 IEEE 31st International Conference on Tools with Artificial Intelligence (ICTAI)10.1109/ICTAI.2019.00016(50-58)Online publication date: Nov-2019
https://doi.org/10.1109/ICTAI.2019.00016
Correas JMartn SSenz-Prez F(2018)Enhancing set constraint solvers with bound consistencyExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.09.05692:C(485-494)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1016/j.eswa.2017.09.056
EstÉvez-martÍn SHortalÁ-gonzÁlez TRodrÍguez-artalejo MDel vado-vÍrseda RSÁenz-pÉrez FFernÁndez A(2009)On the cooperation of the constraint domains ℋ, ℛ, and ℱ in cflpTheory and Practice of Logic Programming10.1017/S14710684090037809:4(415-527)Online publication date: 1-Jul-2009
https://dl.acm.org/doi/10.1017/S1471068409003780
Fernández A(2004)A Generic, Collaborative Framework for Interval Constraint SolvingAI Communications10.5555/1218715.121871917:3(171-174)Online publication date: 1-Aug-2004
https://dl.acm.org/doi/10.5555/1218715.1218719

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents