zbMATH — the first resource for mathematics

Comparing recursion, replication, and iteration in process calculi. (English) Zbl 1098.68086
Díaz, Josep (ed.) et al., Automata, languages and programming. 31st international colloquium, ICALP 2004, Turku, Finland, July 12–16, 2004. Proceedings. Berlin: Springer (ISBN 3-540-22849-7/pbk). Lecture Notes in Computer Science 3142, 307-319 (2004).
Summary: In Lect. Notes Comput. Sci. 2719, 133–144 (2003; Zbl 1039.68082) we provided a discrimination result between recursive definitions and replication in a fragment of CCS by showing that termination (i.e., all computations terminate) is undecidable in the calculus with recursion, whereas it turns out to be decidable in the calculus with replication. Here we extend the results in [loc. cit.] by considering iteration, a third mechanism for expressing infinite behaviours. We show that convergence (i.e., the existence of a terminating computation) is undecidable in the calculus with replication, whereas it is decidable in the calculus with iteration. We also show that recursion, replication and iteration constitute a strict expressiveness hierarchy w.r.t. weak bisimulation: namely, there exist weak bisimulation preserving encodings of iteration in replication (and of replication in recursion), whereas there exist no weak bisimulation preserving encoding in the other direction.
For the entire collection see [Zbl 1056.68007].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI