iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1023/A:1009842826135
Confluence and Semantics of Constraint Simplification Rules | Constraints Skip to main content
Springer Nature Link
Log in

Confluence and Semantics of Constraint Simplification Rules

  • Published:
Constraints Aims and scope Submit manuscript

Abstract

Constraint Simplification Rules (CSR) is a subset of the Constraint Handling Rules (CHR) language. CHR is a powerful special-purpose declarative programming language for writing constraint solvers. The CSR subset of CHR forms essentially a committed-choice language consisting of guarded rules with multiple heads that replace constraints by simpler ones until they are solved. This paper gives declarative and operational semantics as well as soundness and completeness results for CSR programs.

We also introduce a notion of confluence for CSR programs. Confluence is an essential syntactical property of any constraint solver. It ensures that the solver will always compute the same result for a given set of constraints independent of which rules are applied. It also means that it does not matter for the result in which order the constraints arrive at the constraint solver.

We give a decidable, sufficient and necessary syntactic condition for confluence of terminating CSR programs. Moreover, as shown in this paper, confluence of a program implies consistency of its logical meaning (under a mild restriction).

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Abdennadher, S. (1997). Operational semantics and confluence of constraint propagation rules. In Third International Conference on Principles and Practice of Constraint Programming, CP97 LNCS, Springer.

    Google Scholar 

  2. Abdennadher, S. (1998). Analyse von regelbasierten Constraintlösern. PhD thesis, Computer Science Institute, LMU Munich (in German).

    Google Scholar 

  3. Aggoun, A., Chan, D., Dufrense, P., Falvey, E., Grant, H., Herold, A., Macartney, G., Maier, M., Miller, D., Perez, B., van Rossum, E., Schimpf, J., Tsahageas, P., & de Villeneuve, D. (1994). ECLiPSe 3.4 User Manual. ECRC Munich.

    Google Scholar 

  4. Abdennadher, A. & Frühwirth, T. (1998). On completion of constraint handling rules. Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP'98), LNCS 1520, Springer.

  5. Abdennadher, S., Frühwirth, T., & Meuss, H. (1996). On confluence of constraint handling rules. In E. Freuder, editor, Proceedings of the Second International Conference on Principles and Practice of Constraint Programming, CP96 LNCS 1118, Springer.

  6. AÏt-Kaci, H. & Podelski, A. (1994). Functions as passive constraints in LIFE. ACM Transactions on Programming Languages and Systems 16:1279–1318.

    Google Scholar 

  7. Codnognet, P. & Diaz, D. (1993). Boolean constraint solving using clp(FD). In Dale Miller, editor, LogicProgramming·Proceedings of the 1993 International Symposium, 525–539, Vancouver, Canada, MIT Press.

    Google Scholar 

  8. Codish, M., Falaschi, M., Marriott, K., & Winsborough, W. (1997). A confluent semantic basis for the analysis of concurrent constraint logic programs. Journal of Logic Programming 30:53–81.

    Google Scholar 

  9. Clark, K. (1978). Logic and Databases 293–322, Plenum Press, New York.

    Google Scholar 

  10. Dershowitz, N., Okada, N., & Sivakumar, G. (1988). Confluence of conditional rewrite systems. In J.-P. Jouannaud and S. Kaplan, editors, Proceedings of the 1st International Workshop on Conditional Term Rewriting Systems LNCS 308:31–44.

  11. Falaschi, M. Gabbrielli, M. Marriott, K., & Palamidessi, C. (1995). Confluence in concurrent constraint programming. In V.S. Alagar and M. Nivat, editors, Proceedings of AMAST '95 LNCS 936, Springer.

  12. Frühwirth, T., Herold, A., Küchenhoff, V., Le Provost, T., Lim, P., Monfroy, E., & Wallace, M. (1992). Constraint logic programming: An informal introduction. In G. Comyn, N. E. Fuchs, and M. J. Ratcliffe, editors, Logic Programming in Action. LNCS 636:3–35, Springer.

  13. Frühwirth, T. (1995). Constraint handling rules. In A. Podelski, editor, Constraint Programming: Basics and Trends. LNCS 910, Springer.

  14. Frühwirth, T. (1998). A Declarative Language for Constraint Systems: Theory and Practice of Constraint Handling Rules. Habilitation, Computer Science Institute, LMU Munich.

    Google Scholar 

  15. Haridi, S., Janson, S.,& Palamidessi, C. (1992). Structural operational semantics of AKL. Future Generation Computer Systems.

  16. Jaffar, J. & Lasseq, J.-L. (1987). Constraint logic programming. In Conference Record of the Fourteenth Annual ACM Symposium on Principles of Programming Languages 111–119.

  17. Jaffar, J. & Maher, M. J. (1994). Constraint logic programming: A survey. Journal of Logic Programming 20:503–581.

    Google Scholar 

  18. Kirchner, C. & Kirchner, H. (1991). Rewriting: Theory and Applications. North-Holland.

  19. Maher, M. J. (1987). Logic semantics for a class of committed-choice programs. In J.-L. Lassez, editor, Proceedings of the Fourth International Conference on Logic Programming 858–876, MIT Press.

  20. Marte, M. (1996). Implementation eines Konfluenz-Tests f¨ur CSR-Programme. Advanced practical thesis, Institute of Computer Science, LMU Munich.

    Google Scholar 

  21. Meuss, H. (1996). Konfluenz von Constraint-Handling-Rules-Programmen. Master's thesis, Institute of Computer Science, LMU Munich.

    Google Scholar 

  22. Marriott, K. & Odersky, M. (1995). A confluent calculus for concurrent constraint programming with guarded choice. In 1st International Conference on Principles and Practice of Constraint Programming, CP95 310–327, Springer.

  23. Marriott, K. & Stuckey, P. (1998). Programming with Constraints: An Introduction. MIT Press.

  24. Newman, M. H. A. (1942). On theories with a combinatorial definition of equivalence. In Annals of Math, 43:223–243.

    Google Scholar 

  25. Plaisted, D. A. (1993). Equational reasoning and term rewriting systems. In D. Gabbay, C. Hogger, J. A. Robinson, and J. Siekmann, editiors, Handbook of Logic in Artificial Intelligence and Logic Programming 1:273–364, Oxford University Press, Oxford.

    Google Scholar 

  26. Saraswat, V. A. (1993). Concurrent Constraint Programming MIT Press, Cambridge.

    Google Scholar 

  27. Shapiro, E. (1989). The family of concurrent logic programming languages. ACM Computing Surveys 21:413–510.

    Google Scholar 

  28. Smolka, G. (1991). Residuation and guarded rules for constraint logic programming. In Digital Equipment Paris Research Laboratory Research Report, France.

  29. Saraswat, V. A., Rinard, & Panangaden, P. The semantic foundations of concurrent constraint programming. In Conference Record of the 18th Annual ACM Symposium on Principles of Programming Languages 333–352, ACM Press.

  30. van Hentenryck, P. (1991). Constraint logic programming. The Knowledge Engineering Review 6:151–194.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, Ludwig-Maximilians-University, Oettingenstrasse 67, D-80538, Munich, Germany

    Slim Abdennadher & Thom Frühwirth

  2. Center for Information and Language Processing, Ludwig-Maximilians-University, Oettingenstrasse 67, D-80538, Munich, Germany

    Holger Meuss

Authors
  1. Slim Abdennadher
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Thom Frühwirth
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Holger Meuss
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Abdennadher, S., Frühwirth, T. & Meuss, H. Confluence and Semantics of Constraint Simplification Rules. Constraints 4, 133–165 (1999). https://doi.org/10.1023/A:1009842826135

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1009842826135

Search

Navigation