Nothing Special   »   [go: up one dir, main page]

skip to main content
article

A brief history of process algebra

Published: 23 May 2005 Publication History

Abstract

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.

References

[1]
{1} M. Abadi, A.D. Gordon, A calculus for cryptographic protocols: the spi calculus, in: Fourth ACM Conf. on Computer and Communications Security, ACM Press, New York, 1997, pp. 36-47.]]
[2]
{2} L. Aceto, Some of my favorite results in classic process algebra, Tech. Report NS-03-2, BRICS, 2003.]]
[3]
{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]
{4} L. Aceto, W.J. Fokkink, C. Verhoef, Structural operational semantics, in: Handbook of Process Algebra, North-Holland, Amsterdam, 2001, pp. 197-292.]]
[5]
{5} R. Alur, C. Courcoubetis, N. Halbwachs, T.A. Henzinger, P.-H. Ho, X. Nicollin, A. Olivero, J. Sifakis, S. Yovine, The algorithmic analysis of hybrid systems, Theoret. Comput. Sci. 138 (1995) 3-34.]]
[6]
{6} S. Andova, Probabilistic process algebra, Ph.D. Thesis, Technische Universiteit Eindhoven, 2002.]]
[7]
{7} K.R. Apt, N. Francez, W.P. de Roever, A proof system for communicating sequential processes, TOPLAS 2 (1980) 359-385.]]
[8]
{8} D. Austry, G. Boudol, Algèbre de processus et synchronisation, Theoret. Comput. Sci. 30 (1984) 91-131.]]
[9]
{9} J.C.M. Baeten, The total order assumption, in: S. Purushothaman, A. Zwarico (Eds.), Proc. First North American Process Algebra Workshop, Workshops in Computing, Springer, Berlin, 1993, pp. 231-240.]]
[10]
{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]
{11} J.C.M. Baeten, J.A. Bergstra, Real time process algebra, Formal Aspects Comput. 3 (2) (1991) 142-188.]]
[12]
{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]
{13} J.C.M. Baeten, J.A. Bergstra, S.A. Smolka, Axiomatizing probabilistic processes: ACP with generative probabilities, Inform. Comput. 121 (2) (1995) 234-255.]]
[14]
{14} J.C.M. Baeten, C.A. Middelburg, Process Algebra with Timing, EATCS Monographs, Springer, Berlin, 2002.]]
[15]
{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]
{16} J.C.M. Baeten, W.P. Weijland, Process Algebra, Vol. 18, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, Cambridge, 1990.]]
[17]
{17} J.W. de Bakker, J.I. Zucker, Denotational semantics of concurrency, in: Proc. 14th Symp. on Theory of Computing, ACM, New York, 1982, pp. 153-158.]]
[18]
{18} J.W. de Bakker, J.I. Zucker, Processes and the denotational semantics of concurrency, Inform. Control 54 (1982) 70-120.]]
[19]
{19} H. Bekič, Towards a mathematical theory of processes, Tech. Report TR 25.125, IBM Laboratory Vienna, 1971.]]
[20]
{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]
{21} J.A. Bergstra, J.W. Klop, Fixed point semantics in process algebra, Tech. Report IW 208, Mathematical Centre, Amsterdam, 1982.]]
[22]
{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.]]
[23]
{23} J.A. Bergstra, J.W. Klop, Process algebra for synchronous communication, Inform. Control 60 (1,3) (1984) 109-137.]]
[24]
{24} J.A. Bergstra, J.W. Klop, A convergence theorem in process algebra, in: J.W. de Bakker, J.J.M.M. Rutten (Eds.), Ten Years of Concurrency Semantics, World Scientific, Singapore, 1992, pp. 164-195.]]
[25]
{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.]]
[26]
{26} J.A. Bergstra, A. Ponse, S.A. Smolka (Eds.), Handbook of Process Algebra, North-Holland, Amsterdam, 2001.]]
[27]
{27} M. Bernardo, R. Gorrieri, A tutorial on EMPA: A theory of concurrent processes with non-determinism, priorities, probabilities and time, Theoret. Comput. Sci. 202 (1998) 1-54.]]
[28]
{28} E. Best, R. Devillers, M. Koutny, A unified model for nets and process algebras, in: Handbook of Process Algebra, North-Holland, Amsterdam, 2001, pp. 945-1045.]]
[29]
{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]
{30} S.D. Brookes, C.A.R. Hoare, A.W. Roscoe, A theory of communicating sequential processes, J. ACM 31 (3) (1984) 560-599.]]
[31]
{31} O. Burkart, D. Caucal, F. Moller, B. Steffen, Verification on infinite structures, in: Handbook of Process Algebra, North-Holland, Amsterdam, 2001, pp. 545-623.]]
[32]
{32} L. Cardelli, A.D. Gordon, Mobile ambients, Tbeoret. Comput. Sci. 240 (2000) 177-213.]]
[33]
{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.]]
[34]
{34} P.R. D'Argenio, Algebras and automata for timed and stochastic systems, Ph.D. Thesis, University of Twente, 1999.]]
[35]
{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.]]
[36]
{36} E.W. Dijkstra, Guarded commands nondeterminacy and formal derivation of programs, Commun. ACM 18 (8) (1975) 453-457.]]
[37]
{37} U. Engberg, M. Nielsen, A calculus of communicating systems with label passing. Tech. Report DAIMI PB-208, Aarhus University, 1986.]]
[38]
{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]
{39} R.W. Floyd, Assigning meanings to programs, in: J.T. Schwartz (Ed.), Proc. Symp. in Applied Mathematics, Mathematical Aspects of Computer Science, American Mathematical Society, Providence, RI, 1967, pp. 19-32.]]
[40]
{40} R. Focardi, R. Gorrieri, A classification of security properties for process algebras, J. Comput. Security 3 (1995) 5-33.]]
[41]
{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]
{42} R.J. van Glabbeek, What is branching time semantics and why to use it? in: M. Nielsen (Ed.), The Concurrency Column, Bulletin of the EATCS 53, 1994, pp. 190-198.]]
[43]
{43} R.J. van Glabbeek, The linear time--branching time spectrum I. The semantics of concrete, sequential processes, in: Handbook of Process Algebra, North-Holland, Amsterdam, 2001, pp. 3-100.]]
[44]
{44} R.J. van Glabbeek, W.P. Weijland, Branching time and abstraction in bisimulation semantics, J. ACM 43 (1996) 555-600.]]
[45]
{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]
{46} J.F. Groote, Process algebra and structured operational semantics, Ph.D. Thesis, University of Amsterdam, 1991.]]
[47]
{47} J.F. Groote, B. Lisser, Computer assisted manipulation of algebraic process specifications. Tech. Report SEN-R0117, CWI, Amsterdam, 2001.]]
[48]
{48} J.F. Groote, M.A. Reniers, Algebraic Process verification, in: Handbook of Process Algebra, North-Holland, Amsterdam, 2001, pp. 1151-1208.]]
[49]
{49} H. Hansson, Time and probability in formal design of distributed systems, Ph.D. Thesis, University of Uppsala, 1991.]]
[50]
{50} M. Hennessy, Algebraic Theory of Processes, MIT Press, Cambridge, MA, 1988.]]
[51]
{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.]]
[52]
{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]
{53} J. Hillston, A compositional approach to performance modelling, Ph.D. Thesis, Cambridge University Press, Cambridge, 1996.]]
[54]
{54} C.A.R. Hoare, An axiomatic basis for computer programming, Commun. ACM 12 (1969) 576-580.]]
[55]
{55} C.A.R. Hoare, Communicating sequential processes, Commun. ACM 21 (8) (1978) 666-677.]]
[56]
{56} C.A.R. Hoare, A model for communicating sequential processes, in: R.M. McKeag, A.M. Macnaghten (Eds.), On the Construction of Programs, Cambridge University Press, Cambridge, 1980, pp. 229-254.]]
[57]
{57} C.A.R. Hoare, Communicating Sequential Processes, Prentice-Hall, Englewood Cliffs, NJ, 1985.]]
[58]
{58} K.G. Larsen, P. Pettersson, Wang Yi, Uppaal in a nutshell, J. Software Tools Technol Transfer 1 (1997).]]
[59]
{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]
{60} P. Linz, An Introduction to Formal Languages and Automata, Jones and Bartlett, 2001.]]
[61]
{61} G. Lowe, Probabilities and priorities in timed CSP Ph.D. Thesis, University of Oxford, Oxford, 1993.]]
[62]
{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]
{63} S. MacLane, G. Birkhoff, Algebra, MacMillan, New York, 1967.]]
[64]
{64} S. Mauw, PSF: a process specification formalism, Ph.D. Thesis, University of Amsterdam, 1991. See http://carol.science.uva.nl/psf/.]]
[65]
{65} S. Mauw, M.A. Reniers, An algebraic semantics for basic message sequence charts, Comput. J. 37 (1994) 269-277.]]
[66]
{66} A. Mazurkiewicz, Concurrent program schemes and their interpretations, Tech. Report DAIMI PB-78, Aarhus University, 1977.]]
[67]
{67} J. McCarthy, A basis for a mathematical theory of computation, in: P. Braffort, D. Hirshberg (Eds.), Computer Programming and Formal Systems, North-Holland, Amsterdam, 1963, pp. 33-70.]]
[68]
{68} G.J. Milne, CIRCAL: a calculus for circuit description, Integration 1 (1983) 121-160.]]
[69]
{69} G.J. Milne, R. Milner, Concurrent processes and their syntax, J. ACM 26 (2) (1979) 302-321.]]
[70]
{70} R. Milner, An approach to the semantics of parallel programs, in: Proc. Convegno di informatica Teoretica, Pisa, Instituto di Elaborazione della Informazione, 1973, pp. 285-301.]]
[71]
{71} R. Milner, Processes: a mathematical model of computing agents, in: H.E. Rose, J.C. Shepherdson (Eds.), Proc. Logic Colloquium, Studies in Logic and the Foundations of Mathematics, Vol. 80, North-Holland, Amsterdam, 1975, pp. 157-171.]]
[72]
{72} R. Milner, Algebras for communicating systems, in: Proc. AFCET/SMF joint colloq. Applied Mathematics, Paris, 1978.]]
[73]
{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.]]
[74]
{74} R. Milner, Flowgraphs and flow algebras, J. ACM 26 (4) (1979) 794-818.]]
[75]
{75} R. Milner, A Calculus of Communicating Systems, Lecture Notes in Computer Science, Vol. 92, Springer, Berlin, 1980.]]
[76]
{76} R. Milner, Calculi for synchrony and asynchrony, Theoret. Comput. Sci. 25 (1983) 267-310.]]
[77]
{77} R. Milner, A complete inference system for a class of regular behaviours, J. Comput. System Sci. 28 (1984) 439-466.]]
[78]
{78} R. Milner, Communication and Concurrency, Prentice-Hall, Englewood Cliffs, NJ, 1989.]]
[79]
{79} R. Milner, Calculi for interaction, Acta Informatica 33 (1996) 707-737.]]
[80]
{80} R. Milner, Communicating and Mobile Systems: the π-Calculus, Cambridge University Press, Cambridge, 1999.]]
[81]
{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.]]
[82]
{82} R. Milner, J. Parrow, D. Walker, A calculus of mobile processes, Inform. Comput. 100 (1992) 1-77.]]
[83]
{83} F. Moller, P. Stevens, Edinburgh Concurrency Workbench User Manual (Version 7.1) available from http: //www.dcs.ed.ac.uk/home/cwb/]]
[84]
{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]
{85} X. Nicollin, J. Sifakis, The algebra of timed processes ATP: theory and application, Inform. Comput. 114 (1994) 131-178.]]
[86]
{86} S. Owicki, D. Gries, Verifying properties of parallel programs: an axiomatic approach, Commun. ACM 19 (1976) 279-285.]]
[87]
{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]
{88} C.A. Petri, Kommunikation mit antomaten. Ph.D. Thesis, Institut fuer Instrumentelle Mathematik, Bonn, 1962.]]
[89]
{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]
{90} G.D. Plotkin, A powerdomain construction, SIAM J. Comput. 5 (1976) 452-487.]]
[91]
{91} G.D. Plotkin, A structural approach to operational semantics, Tech. Report DAIMI FN-19, Aarhus University, 1981. Reprinted as {93}.]]
[92]
{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).]]
[93]
{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).]]
[94]
{94} A. Pnueli, The temporal logic of programs, in: Proc. 19th Symp. on Foundations of Computer Science, IEEE, 1977, pp. 46-57.]]
[95]
{95} C. Priami, A. Regev, W. Silverman, E. Shapiro, Application of stochastic process algebras to bioinformatics of molecular processes, Inform. Process. Lett. 80 (2001) 25-31.]]
[96]
{96} G.M. Reed, A.W. Roscoe, A timed model for communicating sequential processes, Theoret. Comput. Sci. 58 (1988) 249-261.]]
[97]
{97} M. Rein, 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.]]
[98]
{98} S.A. Schneider, Concurrent and real-time systems (the CSP approach), Worldwide Series in Computer Science, Wiley, New York, 2000.]]
[99]
{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.]]
[100]
{100} D.S. Scott, C. Strachey, Towards a mathematical semantics for computer languages, in: J. Fox (Ed.), Proc. Symp. Computers and Automata, Polytechnic Institute of Brooklyn Press, 1971, pp. 19-46.]]
[101]
{101} Y.S. Usenko, Linearization in µCRL, Ph.D. Thesis, Technische Universiteit Eindhoven, 2002.]]
[102]
{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]
{103} B. Victor, A verification tool for the polyadic π-Calculus, Licentiate Thesis, Department of Computer Systems, Uppsala University, Sweden, May 1994, available as report DoCS 94/50.]]
[104]
{104} T.A.C. Willemse, Semantics and verification in process algebras with data and timing, Ph.D. Thesis, Technische Universiteit Eindhoven, 2003.]]
[105]
{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]
{106} S. Yovine, Kronos: a verification tool for real-time systems, J. Software Tools Technology Transfer 1 (1997) 123-133.]]
[107]
{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.]]

Cited By

View all
  • (2023)Mechanization of the Ravenscar Profile in CoqACM SIGAda Ada Letters10.1145/3631483.363150143:1(106-110)Online publication date: 31-Oct-2023
  • (2023)Type-Safe Dynamic Placement with First-Class Placed ValuesProceedings of the ACM on Programming Languages10.1145/36228737:OOPSLA2(2142-2170)Online publication date: 16-Oct-2023
  • (2023)Macroprogramming: Concepts, State of the Art, and Opportunities of Macroscopic Behaviour ModellingACM Computing Surveys10.1145/357935355:13s(1-37)Online publication date: 13-Jul-2023
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science
Theoretical Computer Science  Volume 335, Issue 2-3
Process algebra
23 May 2005
275 pages

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 23 May 2005

Author Tags

  1. history
  2. process algebra

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 18 Dec 2024

Other Metrics

Citations

Cited By

View all

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media