×

zbMATH — the first resource for mathematics

Truly concurrent constraint programming. (English) Zbl 1002.68026
We study “causality” relationships in concurrent constraint programming: what is observed is not just the conjunction of constraints deposited in the store, but also the causal dependencies between these constraints. We describe a denotational semantics for cc that is fully abstract with respect to observing this “causality” relation on constraints. This semantics preserves more fine-grained structure of computation; in particular the interleaving law \((a\rightarrow P)\parallel(b\rightarrow Q)=(a\rightarrow (P\parallel(b\rightarrow Q)))(b\rightarrow(Q\parallel(a\rightarrow P)))\) is not verified (\(\square\) is indeterminate choice). Relationships between such a denotational approach to true concurrency and different powerdomain constructions are explored.

MSC:
68N19 Other programming paradigms (object-oriented, sequential, concurrent, automatic, etc.)
PDF BibTeX Cite
Full Text: DOI
References:
[1] Abramsky, S., Domain theory in logical form, Ann. pure appl. logic, 51, 1-77, (1991) · Zbl 0737.03006
[2] L. Aceto, M. Hennessy, Towards action-refinement in process algebras, Proc. 4th Annu. Symp. on Logic in Computer Science, IEEE Computer Society Press, Silverspring, MD, 1989, pp. 138-145. · Zbl 0716.68034
[3] G. Boudol, I. Castellani, M.C. Hennessy, A. Kiehn, A theory of processes with localities, Proc. Internat. Conf. on Concurrency Theory, Lecture Notes in Computer Science, vol. 630, 1992, pp. 108-122. · Zbl 0806.68070
[4] F.S. de Boer, M. Gabrielli, E. Marchiori, C. Palamidessi, Proving concurrent programs correct, Proc. 21st ACM SIGPLAN-SIGACT Symp. on Principles of Programming Languages, 1994, pp. 98-108.
[5] F.S. de Boer, C. Palamidessi, A fully abstract model for concurrent constraint programming, Proc. TAPSOFT/CAAP, Lecture Notes in Computer Science, vol. 493, 1991, pp. 296-319. · Zbl 0967.68516
[6] F.S. de Boer, C. Palamidessi, E. Best, Concurrent constraint programming with information removal, Proc. Concurrent Constraint Programming Workshop, Venice, 1995, pp. 1-13.
[7] deKleer, J., An assumption based TMS, Artificial intelligence, 28, 127-162, (1986)
[8] de Nicola, R.; Hennessy, M.C.B., Testing equivalences for processes, Theoret. comput. sci., 34, 83-133, (1984) · Zbl 0985.68518
[9] M. Fromherz, V. Saraswat, Model-based computing: Using concurrent constraint programming for modeling and model compilation, Principles and Practices of Constraint Programming, Lecture Notes in Computer Science, vol. 976, Springer, Berlin, 1995, pp. 629-635.
[10] R. Gorrieri, Refinement atomicity, and transactions for process description languages, Ph.D. Thesis, University of Pisa, 1991.
[11] P. Van Hentenryck, V.A. Saraswat, Y. Deville, Constraint processing in cc(fd), Tech. Report, Computer Science Department, Brown University, 1992. · Zbl 0920.68026
[12] R. Jagadeesan, P. Panangaden, K. Pingali, A fully-abstract semantics for a functional language with logic variables, ACM Trans. Programming Languages Systems 13(4) (1991) 577-625; Proc. 4th IEEE Symp. on Logic in Computer Science, June 1989 (preliminary version). · Zbl 0716.68061
[13] Z. Manna, A. Pnueli, The Temporal Logic of Reactive and Concurrent Systems, Springer, Berlin, 1991, 427 pp. · Zbl 0753.68003
[14] U. Montanari, F. Rossi, True concurrency semantics for concurrent constraint programming, in: V. Saraswat, K. Ueda (Eds.), Proc. 1991 Internat. Logic Programming Symp., 1991.
[15] U. Montanari, F. Rossi, A concurrent semantics for concurrent constraint programs via contextual nets, Principles and Practices of Constraint Programming, 1995, pp. 3-27.
[16] Plotkin, G.D., A powerdomain construction, SIAM J. comput., 5, 3, 452-487, (1976) · Zbl 0355.68015
[17] G.D. Plotkin, Domains. Available from , 1983.
[18] Pratt, V.R., Modeling concurrency with partial orders, Int. J. parallel programming, 15, 1, 33-71, (1986) · Zbl 0622.68034
[19] V.A. Saraswat, The category of constraint systems is Cartesian-closed, Proc. 7th IEEE Symp. on Logic in Computer Science, Santa Cruz, 1992.
[20] Saraswat, V.A., Concurrent constraint programming, doctoral dissertation award and logic programming series, (1993), MIT Press Cambridge, MA
[21] Saraswat, V.A.; Jagadeesan, R.; Gupta, V., Programming in timed concurrent constraint languages, (), 367-413 · Zbl 0942.68539
[22] Smyth, M.B., Powerdomains, J. comput. system sci., 16, 23-36, (1978) · Zbl 0408.68017
[23] V.A. Saraswat, M. Rinard, Concurrent constraint programming, Proc. 17th ACM Symp. on Principles of Programming Languages, San Fransisco, January 1990.
[24] V.A. Saraswat, M. Rinard, P. Panangaden, Semantic foundations of concurrent constraint programming, Proc. 18th ACM Symp. on Principles of Programming Languages, Orlando, January 1991, pp. 333-352.
[25] R. van Glabbeek, F. Vaandrager, Petri net models for algebraic theories of concurrency, Proc. of PARLE, Lecture Notes in Computer Science, vol. 259, 1987, pp. 224-242. · Zbl 0633.68054
[26] W. Vogler, Modular Construction and Partial Order Semantics of Petri Nets, Lecture Notes in Computer Science, vol. 625, Springer, Berlin, 1992, 252pp. · Zbl 1293.68015
[27] G. Winskel, Event structures, in: Petri Nets: Applications and Relationships to Other Models of Concurrency, Lecture Notes in Computer Science, vol. 255, 1987, pp. 325-392.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.