skip to main content
article

Soft concurrent constraint programming

Published: 01 July 2006 Publication History

Abstract

Soft constraints extend classical constraints to represent multiple consistency levels, and thus provide a way to express preferences, fuzziness, and uncertainty. While there are many soft constraint solving formalisms, even distributed ones, as yet there seems to be no concurrent programming framework where soft constraints can be handled. In this article we show how the classical concurrent constraint (cc) programming framework can work with soft constraints, and we also propose an extension of cc languages which can use soft constraints to prune and direct the search for a solution. We believe that this new programming paradigm, called soft cc (scc), can be also very useful in many Web-related scenarios. In fact, the language level allows Web agents to express their interaction and negotiation protocols, and also to post their requests in terms of preferences, and the underlying soft constraint solver can find an agreement among the agents even if their requests are incompatible.

References

[1]
Awduche, D., Malcolm, J., Agogbua, J., O'Dell, M., and McManus, J. 1999. Rfc2702: Requirements for traffic engineering over MPLS. Tech. rep. Network Working Group.]]
[2]
Bella, G. and Bistarelli, S. 2001. Soft constraints for security protocol analysis: Confidentiality. In Proceedings of the 3rd International Symposium on Practical Aspects of Declarative Languages (PADL'01). Lecture Notes in Computer Science, vol. 1990. Springer, Berlin, Germany, 108--122.]]
[3]
Bella, G. and Bistarelli, S. 2002. Confidentiality levels and deliberate/indeliberate protocol attacks. In Proceedings of the 10th Cambridge International Security Protocol Workshop (CISPW2002). Lecture Notes in Computer Science, vol. 2845. Springer, Berlin, Germany, 104--119.]]
[4]
Bistarelli, S. 2001. Soft constraint solving and programming: A general framework. Ph.D. dissertation. Dipartimento di Informatica, Università di Pisa, Pisa, Italy.]]
[5]
Bistarelli, S. and Foley, S. 2003a. Analysis of integrity policies using soft constraints. In Proceedings of the IEEE 4th international Workshop on Policies for Distributed Systems and Networks (POLICY2003). IEEE Computer Society Press, Los Alamitos, CA, 77--80.]]
[6]
Bistarelli, S. and Foley, S. 2003b. A constraint framework for the qualitative analysis of dependability goals: Integrity. In Proceedings of the 22th International Conference on Computer Safety, Reliability and Security (SAFECOMP2003). Lecture Notes in Computer Science, vol. 2788. Springer, Berlin Germany, 130--143.]]
[7]
Bistarelli, S., Montanari, U., and Rossi, F. 1995. Constraint solving over semirings. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI95). Morgan Kaufman, San Francisco, CA, 624--630.]]
[8]
Bistarelli, S., Montanari, U., and Rossi, F. 1997. Semiring-based constraint solving and optimization. J. Assoc. Comput. Mach. 44, 2, 201--236.]]
[9]
Bistarelli, S., Montanari, U., and Rossi, F. 2001. Semiring-based constraint logic programming: Syntax and semantics. ACM Trans. Programm. Lang. Syst. 23, 1, 1--29.]]
[10]
Boer, F. D. and Palamidessi, C. 1991. A fully abstract model for concurrent constraint programming. In Proceedings of the Colloquium on Trees in Algebra and Programming (CAAP91). Lecture Notes in Computer Science, vol. 493. Springer, Berlin, Germany, 296--319.]]
[11]
Calisti, M. and Faltings, B. 2000. Distributed constrained agents for allocating service demands in multi-provider networks. J. Italian Operat. Res. Soc. Special issue on constraint-based problem solving. XXIX, 91.]]
[12]
Chen, S. and Nahrstedt, K. 1998. Distributed QoS routing with imprecise state information. In Proceedings of the 7th IEEE International Conference on Computer, Communications and Networks (ICCCN'98). 614--621.]]
[13]
Clark, D. 1989. Rfc1102: Policy routing in internet protocols. Tech. rep. Network Working Group.]]
[14]
de Boer, F. and Palamidessi, C. 1994. From concurrent logic programming to concurrent constraint programming. In Advances in Logic Programming Theory. Oxford University Press, Oxford, U.K., 55--113.]]
[15]
De Nicola, R., Ferrari, G., Montanari, U., Pugliese, R., and Tuosto, E. 2003. A formal basis for reasoning on programmable QoS. In Verification---Theory and Practice, N. Dershowitz, Ed. Lecture Notes in Computer Science, vol. 2772. Springer, Berlin, Germany, 436--479.]]
[16]
Dubois, D., Fargier, H., and Prade, H. 1993. The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction. In Proceedings of the IEEE International Conference on Fuzzy Systems. IEEE Computer Society Press, Los Alamitos, CA, 1131--1136.]]
[17]
Fargier, H. and Lang, J. 1993. Uncertainty in constraint satisfaction problems: A probabilistic approach. In Proceedings of the European Conference on Symbolic and Qualitative Approaches to Reasoning and Uncertainty (ECSQARU). Lecture Notes in Computer Science, vol. 747. Springer, Berlin, Germany, 97--104.]]
[18]
Freuder, E. and Wallace, R. 1992. Partial constraint satisfaction. Artific. Intell. 58, 21--70.]]
[19]
Jain, R. and Sun, W. 2000. QoS/policy/constraintnbased routing. In Carrier IP Telephony 2000 Comprehensive Report. International Engineering Consortium, Chicago, IL.]]
[20]
Nicola, R. D., Ferrari, G. L., and Pugliese, R. 1998. Klaim: A kernel language for agent interaction and mobility. IEEE Trans. Softw. Eng. (Special issue on mobility and network aware computing) 24, 5, 315--330.]]
[21]
Plotkin, G. 1981. Post-graduate lecture notes in advanced domain theory (incorporating the Pisa lecture notes). Technical rep. Department of Computer Science, University of Edinburgh, Edinbur, Scotland.]]
[22]
Ruttkay, Z. 1994. Fuzzy constraint satisfaction. In Proceedings of the 3rd IEEE International Conference on Fuzzy Systems. 1263--1268.]]
[23]
Saraswat, V. 1993. Concurrent Constraint Programming. MIT Press, Cambridge, MA.]]
[24]
Saraswat, V., Rinard, M., and Panangaden, P. 1991. Semantic foundations of concurrent constraint programming. In Proceedings of the 18th ACM Symposium on Principles of Programming Languages (POPL91). ACM Press, New York, NY, 333--352.]]
[25]
Schiex, T. 1992. Possibilistic constraint satisfaction problems, or “how to handle soft constraint ”? In Proceedings of the 8th Conference of Uncertainty in Artificial Intelligence (UAI92). Morgan Kaufmann, San Francisco, CA, 269--275.]]
[26]
Schiex, T., Fargier, H., and Verfaille, G. 1995. Valued constraint satisfaction problems: Hard and easy problems. In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI95). Morgan Kaufmann, San Francisco, CA, 631--637.]]
[27]
Scott, D. 1982. Domains for denotational semantics. In Proceedings of the 9th International Colloquium on Automata, Languages and Programming (ICALP82). Lecture Notes in Computer Science, vol. 140. Springer, Berlin, Germany, 577--613.]]

Cited By

View all
  • (2024)Local Spaces in Soft Concurrent Constraint Programming Oriented to SecurityLeveraging Applications of Formal Methods, Verification and Validation. REoCAS Colloquium in Honor of Rocco De Nicola10.1007/978-3-031-73709-1_23(373-391)Online publication date: 27-Oct-2024
  • (2022)Soft Concurrent Constraint Programming with Local VariablesCoordination Models and Languages10.1007/978-3-031-08143-9_10(159-177)Online publication date: 13-Jun-2022
  • (2021)Soft constraint automata with memoryJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2020.100615118(100615)Online publication date: Jan-2021
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic
ACM Transactions on Computational Logic  Volume 7, Issue 3
July 2006
192 pages
ISSN:1529-3785
EISSN:1557-945X
DOI:10.1145/1149114
Issue’s Table of Contents
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 July 2006
Published in TOCL Volume 7, Issue 3

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Constraints
  2. concurrent constraint programming
  3. soft constraints

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)13
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Local Spaces in Soft Concurrent Constraint Programming Oriented to SecurityLeveraging Applications of Formal Methods, Verification and Validation. REoCAS Colloquium in Honor of Rocco De Nicola10.1007/978-3-031-73709-1_23(373-391)Online publication date: 27-Oct-2024
  • (2022)Soft Concurrent Constraint Programming with Local VariablesCoordination Models and Languages10.1007/978-3-031-08143-9_10(159-177)Online publication date: 13-Jun-2022
  • (2021)Soft constraint automata with memoryJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2020.100615118(100615)Online publication date: Jan-2021
  • (2019)Polyadic Soft ConstraintsThe Art of Modelling Computational Systems: A Journey from Logic and Concurrency to Security and Privacy10.1007/978-3-030-31175-9_14(241-257)Online publication date: 4-Nov-2019
  • (2018)Soft Constraint Automata with MemoryIt's All About Coordination10.1007/978-3-319-90089-6_6(70-85)Online publication date: 7-Apr-2018
  • (2017)On subexponentials, focusing and modalities in concurrent systemsTheoretical Computer Science10.1016/j.tcs.2017.06.009693(35-58)Online publication date: Sep-2017
  • (2017)Observational and behavioural equivalences for soft concurrent constraint programmingJournal of Logical and Algebraic Methods in Programming10.1016/j.jlamp.2017.06.00192(45-63)Online publication date: Nov-2017
  • (2015)Dynamic Programming on Nominal GraphsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.181.6181(80-96)Online publication date: 10-Apr-2015
  • (2015)Subexponential concurrent constraint programmingTheoretical Computer Science10.1016/j.tcs.2015.06.031606:C(98-120)Online publication date: 16-Nov-2015
  • (2015)A Labelled Semantics for Soft Concurrent Constraint ProgrammingTrust Management IX10.1007/978-3-319-19282-6_9(133-149)Online publication date: 2015
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media