×

zbMATH — the first resource for mathematics

A brief history of process algebra. (English) Zbl 1080.68072
Summary: This note addresses the history of process algebra as an area of research in concurrency theory, the theory of parallel and distributed systems in computer science. Origins are traced back to the early seventies of the twentieth century, and developments since that time are sketched. The author gives his personal views on these matters. He also considers the present situation, and states some challenges for the future.

MSC:
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abadi, M.; Gordon, A.D., A calculus for cryptographic protocolsthe spi calculus, (), 36-47
[2] L. Aceto, Some of my favorite results in classic process algebra, Tech. Report NS-03-2, BRICS, 2003. · Zbl 1169.68533
[3] L. Aceto, Z. Ésik, W.J. Fokkink, A. Ingólfsdóttir (Eds.), Process Algebra: Open Problems and Future Directions, BRICS Notes Series NS-03-3, 2003.
[4] Aceto, L.; Fokkink, W.J.; Verhoef, C., Structural operational semantics, (), 197-292 · Zbl 1062.68074
[5] Alur, R.; Courcoubetis, C.; Halbwachs, N.; Henzinger, T.A.; Ho, P.-H.; Nicollin, X.; Olivero, A.; Sifakis, J.; Yovine, S., The algorithmic analysis of hybrid systems, Theoret. comput. sci., 138, 3-34, (1995) · Zbl 0874.68206
[6] S. Andova, Probabilistic process algebra, Ph.D. Thesis, Technische Universiteit Eindhoven, 2002. · Zbl 0978.68100
[7] Apt, K.R.; Francez, N.; de Roever, W.P., A proof system for communicating sequential processes, Toplas, 2, 359-385, (1980) · Zbl 0468.68023
[8] Austry, D.; Boudol, G., Algèbre de processus et synchronisation, Theoret. comput. sci., 30, 91-131, (1984) · Zbl 0533.68026
[9] Baeten, J.C.M., The total order assumption, (), 231-240
[10] J.C.M. Baeten, Over 30 years of process algebra: past, present and future, in: L. Aceto, Z. Ésik, W.J. Fokkink, A. Ingólfsdóttir (Eds.), Process Algebra: Open Problems and Future Directions, Vol. NS-03-3 of BRICS Notes Series, 2003, pp. 7-12.
[11] Baeten, J.C.M.; Bergstra, J.A., Real time process algebra, Formal aspects comput., 3, 2, 142-188, (1991) · Zbl 0719.68020
[12] J.C.M. Baeten, J.A. Bergstra, C.A.R. Hoare, R. Milner, J. Parrow, R. de Simone, The variety of process algebra, Deliverable ESPRIT Basic Research Action 3006, CONCUR, 1991.
[13] Baeten, J.C.M.; Bergstra, J.A.; Smolka, S.A., Axiomatizing probabilistic processesacp with generative probabilities, Inform. comput., 121, 2, 234-255, (1995) · Zbl 0829.60044
[14] Baeten, J.C.M.; Middelburg, C.A., Process algebra with timing, EATCS monographs, (2002), Springer Berlin · Zbl 1021.68063
[15] J.C.M. Baeten, C.A. Middelburg, M.A. Reniers, A new equivalence for processes with timing, Tech. Report CSR 02-10, Eindhoven University of Technology, Computer Science Department, 2002.
[16] J.C.M. Baeten, W.P. Weijland, Process Algebra, Vol. 18, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge, 1990. · Zbl 0716.68002
[17] de Bakker, J.W.; Zucker, J.I., Denotational semantics of concurrency, (), 153-158 · Zbl 0508.68010
[18] de Bakker, J.W.; Zucker, J.I., Processes and the denotational semantics of concurrency, Inform. control, 54, 70-120, (1982) · Zbl 0508.68011
[19] H. Bekič, Towards a mathematical theory of processes, Tech. Report TR 25.125, IBM Laboratory Vienna, 1971.
[20] H. Bekič, Programming Languages and their Definition (Selected Papers edited by C.B. Jones), Lecture Notes in Computer Science, Vol. 177, Springer, Berlin, 1984.
[21] J.A. Bergstra, J.W. Klop, Fixed point semantics in process algebra, Tech. Report IW 208, Mathematical Centre, Amsterdam, 1982. · Zbl 0549.68012
[22] J.A. Bergstra, J.W. Klop, The algebra of recursively defined processes and the algebra of regular processes, in: J. Paredaens (Ed.), Proc. 11th ICALP, Lecture Notes in Computer Science, Vol. 172, Springer, Berlin, 1984, pp. 82-95. · Zbl 0561.68019
[23] Bergstra, J.A.; Klop, J.W., Process algebra for synchronous communication, Inform. control, 60, 1,3, 109-137, (1984) · Zbl 0597.68027
[24] Bergstra, J.A.; Klop, J.W., A convergence theorem in process algebra, (), 164-195 · Zbl 0625.68023
[25] J.A. Bergstra, C.A. Middelburg, Process algebra semantics for hybrid systems, Tech. Report CS-R 03/06, Technische Universiteit Eindhoven, Department of Computer Science, 2003. · Zbl 1080.68073
[26] J.A. Bergstra, A. Ponse, S.A. Smolka (Eds.), Handbook of Process Algebra, North-Holland, Amsterdam, 2001. · Zbl 0971.00006
[27] Bernardo, M.; Gorrieri, R., A tutorial on EMPAA theory of concurrent processes with non-determinism, priorities, probabilities and time, Theoret. comput. sci., 202, 1-54, (1998) · Zbl 0902.68075
[28] Best, E.; Devillers, R.; Koutny, M., A unified model for nets and process algebras, (), 945-1045
[29] E. Brinksma (Ed.), Information Processing Systems, Open Systems Interconnection, LOTOS—A Formal Description Technique Based on the Temporal Ordering of Observational Behaviour, International Standard, ISO, Vol. IS-8807, Geneva, 1989.
[30] Brookes, S.D.; Hoare, C.A.R.; Roscoe, A.W., A theory of communicating sequential processes, J. ACM, 31, 3, 560-599, (1984) · Zbl 0628.68025
[31] Burkart, O.; Caucal, D.; Moller, F.; Steffen, B., Verification on infinite structures, (), 545-623 · Zbl 1035.68067
[32] Cardelli, L.; Gordon, A.D., Mobile ambients, Theoret. comput. sci., 240, 177-213, (2000) · Zbl 0954.68108
[33] P.J.L. Cuijpers, M.A. Reniers, Hybrid process algebra. Tech. Report CS-R 03/07, Technische Universiteit Eindhoven, Department of Computer Science, 2003. · Zbl 1090.68071
[34] P.R. D’Argenio, Algebras and automata for timed and stochastic systems, Ph.D. Thesis, University of Twente, 1999.
[35] J. Desharnais, V. Gupta, R. Jagadeesan, P. Panangaden, Metrics for labeled Markov systems, in: J.C.M. Baeten, S. Mauw (Eds.), Proc. CONCUR’99, Lecture Notes in Computer Science, Vol. 1664, Springer, Berlin, 1999, pp. 258-273. · Zbl 0939.68081
[36] Dijkstra, E.W., Guarded commands nondeterminacy and formal derivation of programs, Commun. ACM, 18, 8, 453-457, (1975) · Zbl 0308.68017
[37] U. Engberg, M. Nielsen, A calculus of communicating systems with label passing. Tech. Report DAIMI PB-208, Aarhus University, 1986.
[38] J.-C. Fernandez, H. Garavel, A. Kerbrat, R. Mateescu, L. Mounier, M. Sighireanu, CADP (CAESAR/ALDEBARAN development package): a protocol validation and verification toolbox, in: R. Alur, T.A. Henzinger (Eds.), Proc. CAV ’96, Lecture Notes in Computer Science, Vol. 1102, Springer, Berlin, 1996, pp. 437-440.
[39] Floyd, R.W., Assigning meanings to programs, (), 19-32 · Zbl 0189.50204
[40] Focardi, R.; Gorrieri, R., A classification of security properties for process algebras, J. comput. security, 3, 5-33, (1995)
[41] R.J. van Glabbeek, The linear time—branching time spectrum II; the semantics of sequential systems with silent moves, in: E. Best (Ed.), Proc. CONCUR ’93, Lecture Notes in Computer Science, Vol. 715, Springer, Berlin, 1993, pp. 66-81.
[42] van Glabbeek, R.J., What is branching time semantics and why to use it?, (), 190-198 · Zbl 0810.68093
[43] van Glabbeek, R.J., The linear time—branching time spectrum I. the semantics of concrete, sequential processes, (), 3-100 · Zbl 1035.68073
[44] van Glabbeek, R.J.; Weijland, W.P., Branching time and abstraction in bisimulation semantics, J. ACM, 43, 555-600, (1996) · Zbl 0882.68085
[45] N. Götz, U. Herzog, M. Rettelbach, Multiprocessor and distributed system design: The integration of functional specification and performance analysis using stochastic process algebras, in: L. Donatiello, R. Nelson (Eds.), Performance Evaluation of Computer and Communication Systems, Lecture Notes in Computer Science, Vol. 729, Springer, Berlin, 1993, pp. 121-146.
[46] J.F. Groote, Process algebra and structured operational semantics, Ph.D. Thesis, University of Amsterdam, 1991.
[47] J.F. Groote, B. Lisser, Computer assisted manipulation of algebraic process specifications. Tech. Report SEN-R0117, CWI, Amsterdam, 2001.
[48] Groote, J.F.; Reniers, M.A., Algebraic process verification, (), 1151-1208 · Zbl 1035.68069
[49] H. Hansson, Time and probability in formal design of distributed systems, Ph.D. Thesis, University of Uppsala, 1991.
[50] Hennessy, M., Algebraic theory of processes, (1988), MIT Press Cambridge, MA · Zbl 0744.68047
[51] M. Hennessy, R. Milner, On observing nondeterminism and concurrency, in: J.W. de Bakker, J. van Leeuwen (Eds.), Proc. 7th ICALP, Lecture Notes in Computer Science, Vol. 85, Springer, Berlin, 1980, pp. 299-309. · Zbl 0441.68018
[52] T.A. Henzinger, P. Ho, H. Wong-Toi, Hy-Tech: the next generation, in: Proc. RTSS, IEEE, New York, 1995, pp. 56-65.
[53] J. Hillston, A compositional approach to performance modelling, Ph.D. Thesis, Cambridge University Press, Cambridge, 1996. · Zbl 1080.68003
[54] Hoare, C.A.R., An axiomatic basis for computer programming, Commun. ACM, 12, 576-580, (1969) · Zbl 0179.23105
[55] Hoare, C.A.R., Communicating sequential processes, Commun. ACM, 21, 8, 666-677, (1978) · Zbl 0383.68028
[56] Hoare, C.A.R., A model for communicating sequential processes, (), 229-254 · Zbl 0841.68042
[57] Hoare, C.A.R., Communicating sequential processes, (1985), Prentice-Hall Englewood Cliffs, NJ · Zbl 0637.68007
[58] Larsen, K.G.; Pettersson, P.; Wang Yi, Uppaal in a nutshell, J. software tools technol. transfer, 1, (1997) · Zbl 1060.68577
[59] I. Lee, P. Bremond-Gregoire, R. Gerber, A process algebraic approach to the specification and analysis of resource-bound real-time systems. Proc. IEEE, 1994 (special issue on real-time).
[60] Linz, P., An introduction to formal languages and automata, (2001), Jones and Bartlett
[61] G. Lowe, Probabilities and priorities in timed CSP. Ph.D. Thesis, University of Oxford, Oxford, 1993.
[62] N. Lynch, R. Segala, F. Vaandrager, H.B. Weinberg, Hybrid I/O automata, in: T. Henzinger, R. Alur, E. Sontag (Eds.), Hybrid Systems III, Lecture Notes in Computer Science, Vol. 1066, Springer, Berlin, 1995.
[63] MacLane, S.; Birkhoff, G., Algebra, (1967), MacMillan New York · Zbl 0153.32401
[64] S. Mauw, PSF: a process specification formalism, Ph.D. Thesis, University of Amsterdam, 1991. See .
[65] Mauw, S.; Reniers, M.A., An algebraic semantics for basic message sequence charts, Comput. J., 37, 269-277, (1994)
[66] A. Mazurkiewicz, Concurrent program schemes and their interpretations, Tech. Report DAIMI PB-78, Aarhus University, 1977.
[67] McCarthy, J., A basis for a mathematical theory of computation, (), 33-70
[68] Milne, G.J., Circala calculus for circuit description, Integration, 1, 121-160, (1983)
[69] Milne, G.J.; Milner, R., Concurrent processes and their syntax, J. ACM, 26, 2, 302-321, (1979) · Zbl 0395.68030
[70] Milner, R., An approach to the semantics of parallel programs, (), 285-301
[71] Milner, R., Processesa mathematical model of computing agents, (), 157-171
[72] R. Milner, Algebras for communicating systems, in: Proc. AFCET/SMF joint colloq. Applied Mathematics, Paris, 1978. · Zbl 0482.68045
[73] R. Milner, Synthesis of communicating behaviour, in: J. Winkowski, (Ed.), Proc. 7th MFCS, Lecture Notes in Computer Science, Vol. 64, Zakopane, Springer, Berlin, 1978, pp. 71-83. · Zbl 0411.68031
[74] Milner, R., Flowgraphs and flow algebras, J. ACM, 26, 4, 794-818, (1979) · Zbl 0421.68025
[75] R. Milner, A Calculus of Communicating Systems, Lecture Notes in Computer Science, Vol. 92, Springer, Berlin, 1980. · Zbl 0452.68027
[76] Milner, R., Calculi for synchrony and asynchrony, Theoret. comput. sci., 25, 267-310, (1983) · Zbl 0512.68026
[77] Milner, R., A complete inference system for a class of regular behaviours, J. comput. system sci., 28, 439-466, (1984) · Zbl 0562.68065
[78] Milner, R., Communication and concurrency, (1989), Prentice-Hall Englewood Cliffs, NJ · Zbl 0683.68008
[79] Milner, R., Calculi for interaction, Acta informatica, 33, 707-737, (1996)
[80] Milner, R., Communicating and mobile systemsthe π-calculus, (1999), Cambridge University Press Cambridge
[81] R. Milner, Bigraphical reactive systems, in: K.G. Larsen, M. Nielsen, (Eds.), Proc. CONCUR ’01, Lecture Notes in Computer Science, Vol. 2154, Springer, Berlin, 2001, pp. 16-35. · Zbl 1006.68080
[82] Milner, R.; Parrow, J.; Walker, D., A calculus of mobile processes, Inform. comput., 100, 1-77, (1992) · Zbl 0752.68037
[83] F. Moller, P. Stevens, Edinburgh Concurrency Workbench User Manual (Version 7.1) available from
[84] F. Moller, C. Tofts, A temporal calculus of communicating systems, in: J.C.M. Baeten, J.W. Klop (Eds.), Proc. CONCUR’90, Lecture Notes in Computer Science, Vol. 458, Springer, Berlin, 1990, pp. 401-415.
[85] Nicollin, X.; Sifakis, J., The algebra of timed processes atptheory and application, Inform. comput., 114, 131-178, (1994) · Zbl 0811.68093
[86] Owicki, S.; Gries, D., Verifying properties of parallel programsan axiomatic approach, Commun. ACM, 19, 279-285, (1976) · Zbl 0322.68010
[87] D.M.R. Park, Concurrency and automata on infinite sequences, in: P. Deussen (Ed.), Proc. 5th GI Conf., Lecture Notes in Computer Science, Vol. 104, Springer, Berlin, 1981, pp. 167-183.
[88] C.A. Petri, Kommunikation mit automaten. Ph.D. Thesis, Institut fuer Instrumentelle Mathematik, Bonn, 1962.
[89] C.A. Petri, Introduction to general net theory, in: W. Brauer (Ed.), Proc. Advanced Course on General Net Theory, Processes and Systems, Lecture Notes in Computer Science, Vol. 84, Springer, Berlin, 1980, pp. 1-20.
[90] Plotkin, G.D., A powerdomain construction, SIAM J. comput., 5, 452-487, (1976) · Zbl 0355.68015
[91] G.D. Plotkin, A structural approach to operational semantics, Tech. Report DAIMI FN-19, Aarhus University, 1981. Reprinted as [93].
[92] G.D. Plotkin, The origins of structural operational semantics. J. Logic Algebraic Programming, 60/61 (2004) 3-15, 2004 (special issue on structural operational semantics). · Zbl 1072.68063
[93] G.D. Plotkin, A structural approach to operational semantics. J. Logic Algebraic Programming, 60/61 (2004) 17-139, 2004 (special issue on structural operational semantics). · Zbl 1082.68062
[94] A. Pnueli, The temporal logic of programs, in: Proc. 19th Symp. on Foundations of Computer Science, IEEE, 1977, pp. 46-57.
[95] Priami, C.; Regev, A.; Silverman, W.; Shapiro, E., Application of stochastic process algebras to bioinformatics of molecular processes, Inform. process. lett., 80, 25-31, (2001)
[96] Reed, G.M.; Roscoe, A.W., A timed model for communicating sequential processes, Theoret. comput. sci., 58, 249-261, (1988) · Zbl 0655.68031
[97] M. Rem, Partially ordered computations, with applications to VLSI design, in: J.W. de Bakker, J. van Leeuwen (Eds.), Foundations of Computer Science IV, Mathematical Centre Tracts, Vol. 159, Mathematical Centre, Amsterdam, 1983, pp. 1-44. · Zbl 0516.68011
[98] Schneider, S.A., Concurrent and real-time systems (the CSP approach), worldwide series in computer science, (2000), Wiley New York
[99] S.A. Schneider, Process algebra and security, in: K.G. Larsen, M. Nielsen (Eds.), Proc. CONCUR ’01, Lecture Notes in Computer Science, Vol. 2154, Springer, Berlin, 2001, pp. 37-38. · Zbl 1006.68709
[100] Scott, D.S.; Strachey, C., Towards a mathematical semantics for computer languages, (), 19-46
[101] Y.S. Usenko, Linearization in \(\mu\)CRL, Ph.D. Thesis, Technische Universiteit Eindhoven, 2002.
[102] F.W. Vaandrager, Process algebra semantics of POOL, in: J.C.M. Baeten (Ed.), Applications of Process Algebra, Cambridge Tracts in Theoretical Computer Science, Vol. 17, Cambridge University Press, Cambridge, 1990, pp. 173-236.
[103] B. Victor, A verification tool for the polyadic \(\pi\)-Calculus, Licentiate Thesis, Department of Computer Systems, Uppsala University, Sweden, May 1994, available as report DoCS 94/50.
[104] T.A.C. Willemse, Semantics and verification in process algebras with data and timing, Ph.D. Thesis, Technische Universiteit Eindhoven, 2003.
[105] W. Yi, Real-time behaviour of asynchronous agents, in: J.C.M. Baeten, J.W. Klop (Eds.), Proc. CONCUR’90, Lecture Notes in Computer Science, Vol. 458, Springer, Berlin, 1990, pp. 502-520.
[106] Yovine, S., Kronosa verification tool for real-time systems, J. software tools technology transfer, 1, 123-133, (1997) · Zbl 1060.68606
[107] D. Zhang, R. Cleaveland, E. Stark, The integrated CWB-NC/PIOAtool for functional verification and performance analysis of concurrent systems, in: H. Garavel, J. Hatcliff (Eds.), Proc. TACAS ’03, Lecture Notes in Computer Science, Vol. 2619, Springer, Berlin, 2003, pp. 431-436. · Zbl 1031.68554
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.