A Timed Linda Language and its Denotational Semantics

• Autorzy: de Boer F. S. , Gabbrielli M. , Meo M. C.
• Języki publikacji: EN

Abstrakty

EN

We introduce a Timed Linda language (T-Linda) which is obtained by a natural timed interpretation of the usual constructs of the Linda model and by adding a simple primitive which allows one to specify time-outs. Parallel execution of processes follows the scheduling policy of interleaving, however maximal parallelism is assumed for actions depending on time. We first define the operational semantics of T-Linda by means of a transition system, then we define a denotational model which is based on timed reactive sequences. The correctness of this model is proved w.r.t. a notion of observables which includes finite traces of actions and input/output pairs.

Słowa kluczowe

EN

Timed Linda Language; operational semantics; denotational model

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2004
• Tom: Vol. 63, nr 4
• Strony: 309--330
• Opis fizyczny: Bibliogr. 33 poz., tab.

Twórcy

autor

de Boer F. S.

• CWI, Kruislaan 413, NL-1098 SJ, Amsterdam, the Netherlands

autor

Gabbrielli M.

• Universit`a di Bologna, Dipartimento di Scienze dell’Informazione, Mura A. Zamboni 7, 40127 Bologna, Italy

autor

Meo M. C.

• Universit`a di Chieti-Pescara, Dipartimento di Scienze, Viale Pindaro 42

Bibliografia

• [1] L. Aceto and D. Murphy. Timing and causality in process algebra. Acta Informatica, 33(4):317-350, 1996.
• [2] J. Baeten and J. Bergstra. Real time process algebra. Formal Aspects of Computing, 3(2):142-188, 1991.
• [3] G. Berry, and G. Gonthier. The esterel programming language: Design, semantics and implementation. Science of Computer Programming, 19(2):87-152, 1992.
• [4] F. S. de Boer, M. Gabbrielli, and M. C. Meo. A Timed CCP Language. Information and Computation, 161(1):45-83, 2000.
• [5] F. S. de Boer, M. Gabbrielli, and M. C. Meo. A Timed Linda Language. In A. Porto and G. Roman, editors, Proc. of 4th International Conference on Coordination Languages and Models, COORDINATION 2000, volume 1906 of Lecture Notes in Computer Science, pages 299-304. Springer-Verlag, 2000.
• [6] F. S. de Boer, M. Gabbrielli, and M. C. Meo. A Denotational Semantics for a Timed Linda Language. In Proc. of 3rd international ACMSIGPLAN conference on Principles and practice of declarative programming, PPDP 01, pages 28-36. ACM Press, 2001.
• [7] F. S. de Boer, J. N. Kok, C. Palamidessi, and J. J. M. M. Rutten. On Blocks: locality and asynchronous communication. In J. W. de Bakker, W. P. de Roever, and G. Rozenberg, editors, Proc. of REX workshop on Semantics: Foundations and Applications, volume 666 of Lecture Notes in Computer Science, pages 73-90. Springer-Verlag, 1992.
• [8] F. S. de Boer, and C. Palamidessi. A Fully Abstract Model for Concurrent Constraint Programming. In S. Abramsky, and T. S. E. Maibaum, editors, Proc. of TAPSOFT/CAAP, volume 493 of Lecture Notes in Computer Science, pages 296-319. Springer-Verlag, 1991.
• [9] P. Bremond-Gregoire, and I. Lee. A Process Algebra of Communicating Shared Resources with Dense Time and Priorities. Theoretical Computer Science, 189(1-2):169-219, 1997.
• [10] A. Brogi, and J. M. Jacquet. Modeling Coordination via Asynchronous Communication. In D. Garlan and D. Le Métayer, editors, Proc. of 2nd International Conference on Coordination Languages and Models, COORDINATION’97, volume 1282 of Lecture Notes in Computer Science, pages 238-255. Springer-Verlag, 1997.
• [11] S. Brookes. A fully abstract semantics of a shared variable parallel language. In M. Y. Vardi, editor, Proc. of 8th Annual IEEE Symposium on Logic In Computer Science, pages 98-109. IEEE Computer Society Press, 1993.
• [12] N. Busi, R. Gorrieri, and G. Zavattaro. A Process Algebraic View of Linda Coordination Primitives. Theoretical Computer Science, 192(2):167-199, 1998.
• [13] N. Busi, R. Gorrieri, and G. Zavattaro. Process Calculi for Coordination: from Linda to JavaSpaces. In T. Rus, editor, Proc. of 8th International Conference on Algebraic Metodology and Software Technology, AMAST 2000, volume 1816 of Lecture Notes in Computer Science, pages 198-212. Springer-Verlag, 2000.
• [14] N. Carriero and D. Gelernter. Linda in Context. Communications of the ACM, 32(4):444-458, 1989.
• [15] B.A. Davey, and H.A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 1990.
• [16] R. De Nicola, G. Ferrari, and R. Pugliese. KLAIM: A Kernel Language for Agents Interaction and Mobility. In IEEE Transactions on Software Engineering, volume 24, pages 315-330, 1998.
• [17] R. De Nicola, and R. Pugliese. Linda-based Applicative and Imperative Process Algebras. Theoretical Computer Science, 238(1-2):389-437, 2000.
• [18] D. Gelernter. Generative Communication in Linda. ACM Transcations on Programming Languages and Systems, TOPLAS, 7(1):80-112, 1985.
• [19] J. F. Groote. Transition System Specifications with Negative Premises. Theoretical Computer Science, 118(2):263-299, 1993.
• [20] M. Hennessy, and T. Regan. A temporal process algebra. Information and Computation, 117:221-239, 1995.
• [21] J.M. Jacquet, K. De Bosschere, and A. Brogi. On Timed Coordination Languages. In A. Porto and G. Roman, editors, Proc. of 4th International Conference on Coordination Languages and Models, volume 1906 of Lecture Notes in Computer Science, pages 81-98. Springer-Verlag, 2000.
• [22] B. Jonsson. A model and a proof system for asynchronous processes. In Proc. of the 4th ACM Symp. On Principles of Distributed Computing, pages 49-58. ACM Press, 1985.
• [23] R. Koymans. Specifying Real-Time Properties with Metric Temporal Logic. Real-Time Systems, 2(4):255-299, 1990.
• [24] M. Nielsen, C. Palamidessi, F. D. Valencia. Temporal Concurrent Constraint Programming: Denotation, Logic and Applications. Nordic Journal of Computing, 9(2):145-188, 2002.
• [25] C. Palamidessi, F. D. Valencia. A Temporal Concurrent Constraint Programming Calculus. In Proc. od CP01. Springer-Verlag, LNCS 2239, 2001.
• [26] V. A. Saraswat, R. Jagadeesan, and V. Gupta. Foundations of Timed Concurrent Constraint Programming. In S. Abramsky, editor, Proc. of the Ninth IEEE Symposium on Logic in Computer Science, LICS 1994, pages 71-80. IEEE Computer Press, 1994.
• [27] V. A. Saraswat, R. Jagadeesan, and V. Gupta. Timed Default Concurrent Constraint Programming. Journal of Symbolic Computation, 22(5-6):475-520, 1996.
• [28] V. A. Saraswat, and M. Rinard. Concurrent constraint programming. In Proc. of 17th Annual ACM Symposium on Principles of Programming Languages, POPL 1990, pages 232-245. ACM Press, 1990.
• [29] V. A. Saraswat, M. Rinard, and P. Panangaden. Semantics foundations of Concurrent Constraint Programming. In Proc. of 18th Annual ACM Symposium on Principles of Programming Languages, POPL 1991, pages 333-352. ACM Press, 1991.
• [30] G. Smolka. The Definition of Kernel Oz. In A. Podelski, editor, Constraint Programming: Basics and Trends, volume 910 of Lecture Notes in Computer Science, pages 251-292. Springer-Verlag, 1995.
• [31] Sun Microsystem, Inc. JavaSpaces Specifications. 1998.
• [32] F. D. Valencia. Reactive Constraint Programming. Technical report, Brics Progress Report, June 2000.
• [33] P.Wyckoff, S.W.McLaughry, T. J. Lehman, and D. A. Ford. TSpaces. IBMSystems Journal, 37(3):454-474, 1998.