Abstract
De Simone showed that a wide class of languages, including CCS, SCCS, CSP and ACP, are expressible up to strong bisimulation equivalence in Meije. He also showed that every recursively enumerable process graph is representable by a Meije expression. Meije in turn is expressible in aprACP (ACP with action prefixing instead of sequential composition).
Vaandrager established that both results crucially depend on the use of unguarded recursion, and its noncomputable consequences. Effective versions of CCS, SCCS, Meije and ACP, not using unguarded recursion, are incapable of expressing all effective De Simone languages. And no effective language can denote all computable process graphs.
In this paper I recreate De Simone’s results in aprACP without using unguarded recursion. The price to be payed for this is the use of a partial recursive communication function and—for the second result— a single constant denoting a simple infinitely branching process. Due to the noncomputable communication function, the version of aprACP employed is still not effective.
However, I also define a wide class of De Simone languages that are expressible in an effective version of aprACP. This class includes the effective versions of CCS, SCCS, ACP, Meije and most other languages proposed in the literature, but not CSP. An even wider class, including CSP, turns out to be expressible in an effective version of aprACP to which an effective relational renaming operator has been added.
This work was supported by ONR under grant number N00014-92-J-1974.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
D. Austry & G. Boudol (1984): Algèbre de processus et synchronisations. Theoretical Computer Science 30(1), pp. 91–131. See also [4].
J.C.M. Baeten, J.A. Bergstra & J.W. Klop (1987): On the consistency of Koomen’s fair abstraction rule. Theoretical Computer Science 51(1/2), pp. 129–176.
J.A. Bergstra & J.W. Klop (1984): The algebra of recursively defined processes and the algebra of regular processes. This volume.
G. Boudol (1985): Notes on algebraic calculi of processes. In K. Apt, editor: Logics and Models of Concurrent Systems, Springer-Verlag, pp. 261–303. NATO ASI Series F13.
S.D. Brookes, C.A.R. Hoare & A.W. Roscoe (1984): A theory of communicating sequential processes. JACM 31(3), pp. 560–599.
J.F. Groote & F.W. Vaandrager (1992): Structured operational semantics and bisimulation as a congruence. Information and Computation 100(2), pp. 202–260.
Yu. I. Manin (1977): A Course in Mathematical Logic, Graduate Texts in Mathematics 53. Springer-Verlag.
R. Milner (1980): A Calculus of Communicating Systems, LNCS 92. Springer-Verlag.
R. Milner (1983): Calculi for synchrony and asynchrony. Theoretical Computer Science 25, pp. 267–310.
G.D. Plotkin (1981): A structural approach to operational semantics. Report DAIMI FN-19, Computer Science Department, Aarhus University.
A. PONSE (1992): Computable processes and bisimulation equivalence. Report CS-R9207, CWI, Amsterdam.
R. de Simone (1984): On Meije and SCCS: infinite sum operators vs. non-guarded definitions. Theoretical Computer Science 30, pp. 133–138.
R. DE Simone (1985): Higher-level synchronising devices in Meije- SCCS. Theoretical Computer Science 37, pp. 245–267. For more details see [12] and: Calculabilité et Expressivité dans l’Algebra de Processus Parallèles Meije, These de 3e cycle, Univ. Paris 7, 1984.
F.W. Vaandrager (1993): Expressiveness results for process algebras. In J.W. de Bakker, W.P. de Roever & G. Rozenberg, editors: Proceedings REX Workshop on Semantics: Foundations and Applications, Beekbergen, The Netherlands, June 1992, LNCS 666, Springer-Verlag, pp. 609–638.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 British Computer Society
About this paper
Cite this paper
van Glabbeek, R. (1995). On the Expressiveness of ACP. In: Ponse, A., Verhoef, C., van Vlijmen, S.F.M. (eds) Algebra of Communicating Processes. Workshops in Computing. Springer, London. https://doi.org/10.1007/978-1-4471-2120-6_8
Download citation
DOI: https://doi.org/10.1007/978-1-4471-2120-6_8
Publisher Name: Springer, London
Print ISBN: 978-3-540-19909-0
Online ISBN: 978-1-4471-2120-6
eBook Packages: Springer Book Archive