Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-25T01:36:47.740Z Has data issue: false hasContentIssue false
  • English
  • Français

Timed soft concurrent constraint programs: An interleaved and a parallel approach

Published online by Cambridge University Press:  06 June 2014

STEFANO BISTARELLI ,
MAURIZIO GABBRIELLI ,
MARIA CHIARA MEO  and
FRANCESCO SANTINI
STEFANO BISTARELLI
Affiliation:
Dipartimento di Matematica e Informatica, Università di Perugia Via Vanvitelli 1, 06123 Perugia, Italy (e-mail: [email protected])
MAURIZIO GABBRIELLI
Affiliation:
Dipartimento di Scienze dell'Informazione, Università di Bologna Via Zamboni 33, 40126 Bologna, Italy (e-mail: [email protected])
MARIA CHIARA MEO
Affiliation:
Dipartimento di Economia, Università “G. D'Annunzio” Viale Pindaro 42, 65127 Pescara, Italy (e-mail: [email protected])
FRANCESCO SANTINI
Affiliation:
Centrum Wiskunde & Informatica (CWI) Science Park 123, 1098XG Amsterdam, The Netherlands (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

We propose a timed and soft extension of Concurrent Constraint Programming. The time extension is based on the hypothesis of bounded asynchrony: The computation takes a bounded period of time and is measured by a discrete global clock. Action prefixing is then considered as the syntactic marker that distinguishes a time instant from the next one. Supported by soft constraints instead of crisp ones, tell and ask agents are now equipped with a preference (or consistency) threshold, which is used to determine their success or suspension. In this paper, we provide a language to describe the agents' behavior, together with its operational and denotational semantics, for which we also prove the compositionality and correctness properties. After presenting a semantics using maximal parallelism of actions, we also describe a version for their interleaving on a single processor (with maximal parallelism for time elapsing). Coordinating agents that need to take decisions on both preference values and time events may benefit from this language.

Keywords

Soft Concurrent Constraint ProgrammingTimed Concurrent Constraint Programminginterleavingparallelism
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 15 , Issue 6 , November 2015 , pp. 743 - 782
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Berry, G. and Gonthier, G. 1992. The ESTEREL synchronous programming language: Design, semantics, implementation. Science of Computer Programming 19, 2, 87–152.CrossRefGoogle Scholar
Bistarelli, S. 2004. Semirings for Soft Constraint Solving and Programming (LNCS). Springer-Verlag, London.CrossRefGoogle Scholar
Bistarelli, S., Gabbrielli, M., Meo, M. C. and Santini, F. 2008. Timed soft concurrent constraint programs. In Proceedings of the 10th International Conference on Coordination Models and Languages, COORDINATION. Lecture Notes in Computer Science, vol. 5052. Springer, London, 50–66.Google Scholar
Bistarelli, S., Montanari, U. and Rossi, F. 1997. Semiring-based constraint satisfaction and optimization. Journal of the ACM 44, 2, 201–236.CrossRefGoogle Scholar
Bistarelli, S., Montanari, U. and Rossi, F. 2006. Soft concurrent constraint programming. ACM Transactions on Computer Logic 7, 3, 563–589.CrossRefGoogle Scholar
Bistarelli, S. and Santini, F. 2011. A non-monotonic soft concurrent constraint language to model the negotiation process. Fundamenta Informaticae 111, 3, 257–279.Google Scholar
Bortolussi, L. 2006. Stochastic concurrent constraint programming. Electronic Notes in Theoretical Computer Science 164, 3, 65–80.CrossRefGoogle Scholar
Brookes, S. D. 1993. Full abstraction for a shared variable parallel language. In Proceedings of 8th Annual IEEE Symposium on Logic in Computer Science, (LICS '93). IEEE Computer Society, Los Alamitos, CA, 98–109.Google Scholar
Busi, N., Gorrieri, R. and Zavattaro, G. 2000. Process calculi for coordination: From Linda to JavaSpaces. In Proceedings of AMAST, LNCS, vol. 1816. Springer-Verlag, London, 198–212.Google Scholar
de Boer, F. S., Gabbrielli, M. and Meo, M. C. 2000. A timed concurrent constraint language. Information and Computation 161, 1, 45–83.CrossRefGoogle Scholar
de Boer, F. S., Gabbrielli, M. and Meo, M. C. 2004. A timed Linda language and its denotational semantics. Fundamenta Informaticae 63, 4, 309–330.Google Scholar
de Boer, F. S. and Palamidessi, C. 1991. A fully abstract model for concurrent constraint programming. In TAPSOFT '91: Proceedings of CAAP '91, vol. 1. Springer-Verlag, New York, NY, 296–319.CrossRefGoogle Scholar
De Nicola, R., Ferrari, G. L., Loreti, M. and Pugliese, R. 2011. A language-based approach to autonomic computing. In 10th International Symposium on Formal Methods for Components and Objects (FMCO), Beckert, B., Damiani, F., de Boer, F. S. and Bonsangue, M. M., Eds. Lecture Notes in Computer Science, vol. 7542. Springer, New York, NY, 25–48.Google Scholar
de Nicola, R., Ferrari, G. L., and Pugliese, R. 1998. KLAIM: A Kernel Language for Agents Interaction and Mobility. IEEE Transactions on Software Engineering 24, 5, 315–330.Google Scholar
Di Pierro, A. and Wiklicky, H. 1998. Probabilistic concurrent constraint programming: Towards a fully abstract model. In Proceedings of Mathematical Foundations of Computer Science (MFCS '98). Springer-Verlag, London, 446–455.Google Scholar
Gallien, J. and Gupta, S. 2007. Temporary and permanent buy out prices in online auctions. Management Science 53, 5, 814–833.Google Scholar
Halbwachs, N., Caspi, P., Raymond, P. and Pilaud, D. 1991. The synchronous data-flow programming language LUSTRE. Proceedings of the IEEE 79, 9, 1305–1320.Google Scholar
Harel, D. 1987. Statecharts: A visual formalism for complex systems. Science of Computer Programming 8, 3, 231–274.CrossRefGoogle Scholar
Jonsson, B. 1985. A model and proof system for asynchronous networks. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC '85). ACM Press, New York, NY, 49–58.CrossRefGoogle Scholar
le Guernic, P., le Borgne, M., Gautier, T. and le Maire, C. 1991. Programming real-time applications with signal. Proceedings of the IEEE 79, 9, 1321–1336.CrossRefGoogle Scholar
Nielsen, M. and Valencia, F. D. 2002. Temporal concurrent constraint programming: Applications and behavior. In Formal and Natural Computing – Essays Dedicated to Grzegorz Rozenberg, Brauer, W., Ehrig, H., Karhumäki, J. and Salomaa, A., Eds. Springer-Verlag, London, 298–324.Google Scholar
Olarte, C., Palamidessi, C. and Valencia, F. 2007. Universal timed concurrent constraint programming. In Proceedings of the 23rd International Conference on Logic Programming (ICLP). LNCS, vol. 4670. Springer, London, 464–465.Google Scholar
Palamidessi, C. and Valencia, F. D. 2001. A temporal concurrent constraint programming calculus. In Proceedings of Principles and Practice of Constraint Programming (CP '01). Springer-Verlag, London, 302–316.Google Scholar
Saraswat, V. 1989. Concurrent Constraint Programming Languages. PhD thesis, Carnegie-Mellon University, Pittsburgh, PA.Google Scholar
Saraswat, V., Jagadeesan, R. and Gupta, V. 1996. Timed default concurrent constraint programming. Journal of Symbolic Computation 22, 5–6, 475–520.CrossRefGoogle Scholar
Saraswat, V. and Rinard, M. 1990. Concurrent constraint programming. In Proceedings of Principles of Programming Languages (POPL '90). ACM Press, New York, NY, 232–245.Google Scholar
Saraswat, V. A., Jagadeesan, R. and Gupta, V. 1994. Foundations of timed concurrent constraint programming. In Proceedings of the Ninth Annual IEEE Symposium on Logic in Computer Science (LICS '94). IEEE Computer Society, Los Alamitos, CA, 71–80.Google Scholar
Valencia, F. D. 2003. Timed concurrent constraint programming: Decidability results and their application to LTL. In 19th International Conference on Logic Programming (ICLP '03). LNCS, vol. 2916. Springer, London, 422–437.Google Scholar