Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Process algebras for Petri nets : the alphabetization of distributed systems
Gorrieri R., Springer International Publishing, New York, NY, 2017. 302 pp. Type: Book (978-3-319555-58-4)
Date Reviewed: Feb 6 2019

This monograph relates process expressions to process models, such as labeled transition systems and Petri nets of various kinds. The models are set up in chapters 2 and 3, together with descriptions of their behavior, such as strong bisimulation, weak bisimulation, and step bisimulation. The “alphabetization” in the title refers to syntactic expressions. “Algebras” refers to the fact that new operators are added one at a time, and it is explicitly studied whether these behavioral equivalences are congruencies under the operators.

Chapter 4 begins with right-linear grammars for finite state machines, credited to Robin Milner. Chapter 5 follows with calculi for finite state nets (which allow multiple tokens) and basic parallel processes (BPP) [1], which add a parallel composition operation. The interesting idea here, credited to Ursula Goltz, is to use process models with multiple tokens (unsafe Petri nets). With the process decompositions of Degano et al. [2] and Olderog [3], this gives a very simple treatment of these two calculi.

Chapters 6 and 7 introduce two calculi with the restriction operator to model two-party and multiparty communication, respectively. The latter goes beyond Milner’s calculus of communicating systems [4] and is closer to Hoare’s communicating sequential processes [5]; both of these earlier books have many motivating examples. The new idea here is to allow for self-synchronization, which may occur because of the net being unsafe. The author argues that this allows for the simple static definition of nets even though there may be an overapproximation of reachability. I think having reentrant code is a good idea. Chapters 8 and 9 extend the syntax to Turing-complete extensions of Petri nets, but I did not read them carefully.

The book is strong on semantics and the examples are mainly to illustrate proofs and constructions. Compared to the author’s earlier textbook [6], which has more modeling examples, this is a dense monograph, but rewarding all the same. The underlying idea of mimicking the Chomsky hierarchy (also found in Moller’s paper [7]) yields very nice results.

There are many ideas in this book, and graduates student will benefit from a careful examination of the constructions, while also looking at other books and papers and comparing them. I lectured on some calculi in this book for a small number of interested undergraduates. Shields’s book [8] gives a detailed treatment using asynchronous transition systems as a basis: these are intermediate models between labeled transition systems and Petri nets, using a distributed alphabet in an effective manner. It would be interesting to make a pedagogic comparison of these two treatments of non-interleaving concurrency.

Reviewer:  K. Lodaya Review #: CR146418 (1904-0090)
1) Christensen, S. Decidability and decomposition in process algebras, PhD thesis. University of Edinburgh, 1993.
2) Degano, P.; De Nicola, R.; Montanari, U. A partial ordering semantics for CCS. Theoretical Computer Science 75, 3(1990), 223–262.
3) Olderog, E.-R. Nets, terms and formulas. Cambridge University Press, Cambridge, UK, 1991.
4) Milner, R. Communication and concurrency. Prentice-Hall, Upper Saddle River, NJ, 1989.
5) Hoare, C. A. R. Communicating sequential processes. Prentice-Hall, Upper Saddle River, NJ, 1985.
6) Gorrieri, R.; Versari, C. An introduction to concurrency theory. Springer, Cham, Switzerland, 2015.
7) Moller, F. A taxonomy of infinite state processes. Electronic Notes in Theoretical Computer Science 18, (1998), 1–20.
8) Shields, M. W. Semantics of parallelism: non-interleaving representation of behaviour. Springer, Berlin, Germany, 1997.
Bookmark and Share
  Reviewer Selected
 
 
Formal Languages (F.4.3 )
 
 
Distributed Programming (D.1.3 ... )
 
 
Petri Nets (D.2.2 ... )
 
 
Process Models (F.3.2 ... )
 
 
Synchronization (D.4.1 ... )
 
 
Threads (D.4.1 ... )
 
  more  
Would you recommend this review?
yes
no
Other reviews under "Formal Languages": Date
The three subfamilies of rational &ohgr;-languages closed under &ohgr;-transduction
Timmerman E. Theoretical Computer Science 76(2-3): 243-250, 2001. Type: Article
Jul 1 1992
Introduction to formal languages
Révész G., Dover Publications, Inc., New York, NY, 1991. Type: Book (9780486666976)
Jan 1 1993
Fibonacci morphisms and Sturmian words
Séébold P. Theoretical Computer Science 88(2): 365-384, 1991. Type: Article
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy