Abstract
We present a labelled semantics for Soft Concurrent Constraint Programming (SCCP), a language where concurrent agents may synchronize on a shared store by either posting or checking the satisfaction of (soft) constraints. SCCP generalizes the classical formalism by parametrising the constraint system over an order-enriched monoid: the monoid operator is not required to be idempotent, thus adding the same information several times may change the store. The novel operational rules are shown to offer a sound and complete co-inductive technique to prove the original equivalence over the unlabelled semantics.
The research has been partially supported by the MIUR PRIN 2010LHT4KM CINA and PRIN 2010XSEMLC “Security Horizons”, by the ANR 12IS02001 PACE, and by the Aut. Reg. of Sardinia P.I.A. 2010 “Social Glue”.
Chapter PDF
Similar content being viewed by others
Keywords
- Constraint Satisfaction Problem
- Soft Constraint
- Label Transition System
- Denotational Semantic
- Compact Element
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Aristizábal, A., Bonchi, F., Palamidessi, C., Pino, L.F., Valencia, F.D.: Deriving labels and bisimilarity for concurrent constraint programming. In: Hofmann, M. (ed.) FOSSACS 2011. LNCS, vol. 6604, pp. 138–152. Springer, Heidelberg (2011)
Arkhangelskii, A.V., Pontryagin, L.S.: General Topology I. Springer (1990)
Baccelli, F., Cohen, G., Olsder, G., Quadrat, J.P.: Synchronization and Linearity: An Algebra for Discrete Event Systems. Wiley (1992)
Bistarelli, S., Gabbrielli, M., Meo, M.C., Santini, F.: Timed soft concurrent constraint programs. In: Lea, D., Zavattaro, G. (eds.) COORDINATION 2008. LNCS, vol. 5052, pp. 50–66. Springer, Heidelberg (2008)
Bistarelli, S., Gadducci, F.: Enhancing constraints manipulation in semiring-based formalisms. In: ECAI 2006. FAIA, vol. 141, pp. 63–67. IOS Press (2006)
Bistarelli, S., Montanari, U., Rossi, F.: Semiring-based constraint satisfaction and optimization. Journal of ACM 44(2), 201–236 (1997)
Bistarelli, S., Montanari, U., Rossi, F.: Soft concurrent constraint programming. ACM Transactions on Computational Logic 7(3), 563–589 (2006)
Bistarelli, S., Santini, F.: A secure non-monotonic soft concurrent constraint language. Fundamamenta Informaticae 134(3-4), 261–285 (2014)
Bonchi, F., Gadducci, F., Monreale, G.V.: Reactive systems, barbed semantics, and the mobile ambients. In: de Alfaro, L. (ed.) FOSSACS 2009. LNCS, vol. 5504, pp. 272–287. Springer, Heidelberg (2009)
Buscemi, M.G., Montanari, U.: CC-pi: A constraint-based language for specifying service level agreements. In: De Nicola, R. (ed.) ESOP 2007. LNCS, vol. 4421, pp. 18–32. Springer, Heidelberg (2007)
Dal Lago, U., Martini, S.: Phase semantics and decidability of elementary affine logic. Theoretical Computer Science 318(3), 409–433 (2004)
Fargier, H., Lang, J.: Uncertainty in constraint satisfaction problems: a probabilistic approach. In: Moral, S., Kruse, R., Clarke, E. (eds.) ECSQARU 1993. LNCS, vol. 747, pp. 97–104. Springer, Heidelberg (1993)
Galatos, N., Jipsen, P., Kowalski, T., Ono, H.: Residuated Lattices: An Algebraic Glimpse at Substructural Logics, vol. 151. Elsevier (2007)
Golan, J.: Semirings and Affine Equations over Them: Theory and Applications. Kluwer (2003)
Karner, G.: Semiring-based constraint satisfaction and optimization. Semigroup Forum 45(XX), 148–165 (1992)
Leifer, J.J., Milner, R.: Deriving bisimulation congruences for reactive systems. In: Palamidessi, C. (ed.) CONCUR 2000. LNCS, vol. 1877, pp. 243–258. Springer, Heidelberg (2000)
Milner, R., Sangiorgi, D.: Barbed bisimulation. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 685–695. Springer, Heidelberg (1992)
Monk, J.D.: An introduction to cylindric set algebras. Logic Journal of IGPL 8(4), 451–496 (2000)
Montanari, U., Sassone, V.: Dynamic congruence vs. progressing bisimulation for CCS. Fundamenta informaticae 16(2), 171–199 (1992)
Pino, L.F., Bonchi, F., Valencia, F.D.: A behavioral congruence for concurrent constraint programming with nondeterministic choice. In: Ciobanu, G., Méry, D. (eds.) ICTAC 2014. LNCS, vol. 8687, pp. 351–368. Springer, Heidelberg (2014)
Saraswat, V.A., Rinard, M.C., Panangaden, P.: Semantic foundations of concurrent constraint programming. In: Wise, D.S. (ed.) POPL 1991, pp. 333–352. ACM Press (1991)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 IFIP International Federation for Information Processing
About this paper
Cite this paper
Gadducci, F., Santini, F., Pino, L.F., Valencia, F.D. (2015). A Labelled Semantics for Soft Concurrent Constraint Programming. In: Holvoet, T., Viroli, M. (eds) Coordination Models and Languages. COORDINATION 2015. Lecture Notes in Computer Science(), vol 9037. Springer, Cham. https://doi.org/10.1007/978-3-319-19282-6_9
Download citation
DOI: https://doi.org/10.1007/978-3-319-19282-6_9
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19281-9
Online ISBN: 978-3-319-19282-6
eBook Packages: Computer ScienceComputer Science (R0)