Abstract
We study the expressive power of restriction and its interplay with replication. We do this by considering several syntactic variants of CCS! (CCS with replication instead of recursion) which differ from each other in the use of restriction with respect to replication. We consider three syntactic variations of CCS! which do not allow the use of an unbounded number of restrictions: CCS\(_{!}^{-!\nu}\) is the fragment of CCS! not allowing restrictions under the scope of a replication. CCS\(_{!}^{-\nu}\) is the restriction-free fragment of CCS!. The third variant is CCS\(_{!+pr}^{-!\nu}\) which extends CCS\(_{!}^{-!\nu}\) with Phillips’ priority guards.
We show that the use of unboundedly many restrictions in CCS! is necessary for obtaining Turing expressiveness in the sense of Busi et al [8]. We do this by showing that there is no encoding of RAMs into CCS\(_{!}^{-!\nu}\) which preserves and reflects convergence. We also prove that up to failures equivalence, there is no encoding from CCS! into CCS\(_{!}^{-!\nu}\) nor from CCS\(_{!}^{-!\nu}\) into CCS\(_{!}^{-\nu}.\) As lemmata for the above results we prove that convergence is decidable for CCS\(_{!}^{-!\nu}\) and that language equivalence is decidable for CCS\(_{!}^{-\nu}\). As corollary it follows that convergence is decidable for restriction-free CCS. Finally, we show the expressive power of priorities by providing an encoding of RAMs in CCS\(_{!+pr}^{-!\nu}\).
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Amadio, R., Meyssonnier, C.: On decidability of the control reachability problem in the asynchronous π−calculus. Nordic Journal of Computing 9(2) (2002)
Aranda, J., Giusto, C.D., Nielsen, M., Valencia, F.D.: CCS with replication in the chomsky hierarchy: The expressive power of divergence. In: Shao, Z. (ed.) APLAS 2007. LNCS, vol. 4807, pp. 383–398. Springer, Heidelberg (2007)
Aranda, J., Valencia, F., Versari, C.: On the expressive power of restriction and priorities in ccs with replication. Technical report, l’École Polytechnique (2008), http://www.lix.polytechnique.fr/Labo/Jesus.Aranda/publications/trccs.pdf
Baeten, J.C.M., Bergstra, J.A., Klop, J.W.: Decidability of bisimulation equivalence for processes generating context-free languages. J. ACM 40(3), 653–682 (1993)
Borger, E., Gradel, E., Gurevich, Y.: The Classical Decision Problem. Springer, Heidelberg (1994)
Brookes, S.D., Hoare, C.A.R., Roscoe, A.W.: A theory of communicating sequential processes. Journal of the ACM 31(3), 560–599 (1984)
Busi, N., Gabbrielli, M., Zavattaro, G.: Replication vs. recursive definitions in channel based calculi. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 133–144. Springer, Heidelberg (2003)
Busi, N., Gabbrielli, M., Zavattaro, G.: Comparing recursion, replication, and iteration in process calculi. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 307–319. Springer, Heidelberg (2004)
Christensen, S.: Decidability and Decomposition in Process Algebras. PhD thesis, Edinburgh University (1993)
Christensen, S., Hirshfeld, Y., Moller, F.: Decidable subsets of ccs. Comput. J. 37(4), 233–242 (1994)
Esparza, J., Nielsen, M.: Decidability issues for petri nets. Technical report, BRICS RS-94-8 (1994)
Giambiagi, P., Schneider, G., Valencia, F.D.: On the expressiveness of infinite behavior and name scoping in process calculi. In: Walukiewicz, I. (ed.) FOSSACS 2004. LNCS, vol. 2987, pp. 226–240. Springer, Heidelberg (2004)
Goltz, U.: Ccs and petri nets. In: Guessarian, I. (ed.) LITP 1990. LNCS, vol. 469, pp. 334–357. Springer, Heidelberg (1990)
Hirshfeld, Y.: Petri nets and the equivalence problem. In: Meinke, K., Börger, E., Gurevich, Y. (eds.) CSL 1993. LNCS, vol. 832, pp. 165–174. Springer, Heidelberg (1994)
Milner, R.: Communication and Concurrency. Prentice-Hall, Englewood Cliffs (1989)
Minsky, M.: Computation: finite and infinite machines. Prentice-Hall, Englewood Cliffs (1967)
Phillips, I.: Ccs with priority guards. J. Log. Algebr. Program. 75(1), 139–165 (2008)
Taubner, D.: Finite representation of CCS and TCSP programs by automata and Petri nets. In: Taubner, D.A. (ed.) Finite Representations of CCS and TCSP Programs by Automata and Petri Nets. LNCS, vol. 369. Springer, Heidelberg (1989)
Versari, C., Busi, N., Gorrieri, R.: On the expressive power of global and local priority in process calculi. In: Caires, L., Vasconcelos, V.T. (eds.) CONCUR 2007. LNCS, vol. 4703, pp. 241–255. Springer, Heidelberg (2007)
Zavattaro, G., Cardelli, L.: Termination problems in chemical kinetics. In: van Breugel, F., Chechik, M. (eds.) CONCUR 2008. LNCS, vol. 5201, pp. 477–491. Springer, Heidelberg (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aranda, J., Valencia, F.D., Versari, C. (2009). On the Expressive Power of Restriction and Priorities in CCS with Replication. In: de Alfaro, L. (eds) Foundations of Software Science and Computational Structures. FoSSaCS 2009. Lecture Notes in Computer Science, vol 5504. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00596-1_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-00596-1_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-00595-4
Online ISBN: 978-3-642-00596-1
eBook Packages: Computer ScienceComputer Science (R0)