Handbook of Process Algebra [Hardcover]

J.A. Bergstra (Editor), A. Ponse (Editor), S.A. Smolka (Editor)

Book Description

Publication Date: March 30, 2001 | ISBN-10: 0444828303 | ISBN-13: 978-0444828309 | Edition: 1

Process Algebra is a formal description technique for complex computer systems, especially those involving communicating, concurrently executing components. It is a subject that concurrently touches many topic areas of computer science and discrete math, including system design notations, logic, concurrency theory, specification and verification, operational semantics, algorithms, complexity theory, and, of course, algebra.
This Handbook documents the fate of process algebra since its inception in the late 1970's to the present. It is intended to serve as a reference source for researchers, students, and system designers and engineers interested in either the theory of process algebra or in learning what process algebra brings to the table as a formal system description and verification technique. The Handbook is divided into six parts spanning a total of 19 self-contained Chapters.
The organization is as follows. Part 1, consisting of four chapters, covers a broad swath of the basic theory of process algebra. Part 2 contains two chapters devoted to the sub-specialization of process algebra known as finite-state processes, while the three chapters of Part 3 look at infinite-state processes, value-passing processes and mobile processes in particular. Part 4, also three chapters in length, explores several extensions to process algebra including real-time, probability and priority. The four chapters of Part 5 examine non-interleaving process algebras, while Part 6's three chapters address process-algebra tools and applications.

Editorial Reviews

Review

J.V. Tucker
For the computer scientist interested in fundamental theory or in design, the Handbook is a treasure house of insights and information......the editors must be congratulated in having created a major landmark in this exciting area of science....
The Computer Journal

Product Details

• Hardcover: 1356 pages
• Publisher: Elsevier Science; 1 edition (March 30, 2001)
• Language: English
• ISBN-10: 0444828303
• ISBN-13: 978-0444828309
• Product Dimensions: 9.1 x 6.5 x 3.1 inches
• Shipping Weight: 4.6 pounds (View shipping rates and policies)
• Average Customer Review: 4.0 out of 5 stars  See all reviews (1 customer review)
• Amazon Best Sellers Rank: #3,451,572 in Books (See Top 100 in Books)

Customer Reviews

Most Helpful Customer Reviews

2 of 3 people found the following review helpful:

4.0 out of 5 stars Helpful overview, March 8, 2006

By 

Dr. Lee D. Carlson (Baltimore, Maryland USA) - See all my reviews
(VINE VOICE)    (HALL OF FAME REVIEWER)    (REAL NAME)   

This review is from: Handbook of Process Algebra (Hardcover)

Process algebra is not only of interest in mathematics, theoretical computer science, and mathematical logic but is of enormous importance in applications. Most of these applications have been in business process modeling, models of concurrent processing, and computational biology. This book gives a fairly comprehensive overview of the main approaches to process algebra, but emphasizing theoretical foundations and not practical applications. One of the process algebras discussed in the book is the pi-calculus, this discussion appearing in Part 3 of the book by Joachim Parrow. This article was the only one read by this reviewer, so the commentary here will deal with it exclusively.

The pi-calculus has been the subject of an enormous amount of research in the last fifteen years, and has found its way into practical applications. It is introduced by the author as a mathematical model of processes with interconnections that change as they interact. The computational paradigm in the pi-calculus is fairly simple: a computation consists of the transfer of a communication link between processes. The process receiving the link can then utilize it to engage in interactions with other processes or agents. If one approaches the pi-calculus with a knowledge of the lambda calculus underlying functional computation, one will find that there are many parts of the pi-calculus that admit an interpretation in the lambda calculus.

There is much more to the pi-calculus however, and the author has given the reader a general discussion of its theoretical foundations. His approach is fairly clear, with many examples given, and he devotes separate sections to the discussion of some of the variants of the pi-calculus. This allows readers to skip these sections if they only want to learn concentrate on the pi-calculus as it was originally conceived (by the researcher Robin Milner).

One of the first things that the author clears up concerns the view that pi-calculus is merely a value-passing process algebra (with the values being the links). Noting that the things that are transferred do not have any internal structure may reinforce this belief, he says. To counter this skepticism he notes that that expressive power of the pi-calculus comes from its ability to migrate `local scopes.' As in other process algebras, one can define a private or `restricted' link between processes in the pi-calculus, but this link can be sent by the processes that share it to another process that can use it. The scope of an object must go along with the object when it is transferred between the processes, and this makes the pi-calculus more than just a value-passing process algebra he argues.

As in other process algebras some processes in the pi-calculus should be viewed as essentially the same if they have the same effective behavior. There are many notions of equivalence of processes in the pi-calculus, but the first one that is discussed by the author concerns the `structural congruence' of processes. This notion is a purely syntactical one, where two processes are structurally congruent if they are the same under a change of bound names (called alpha-conversion in the lambda calculus). Structural congruence also enforces the parallel processes as an Abelian group, and has various scope extension laws.

Another notion of behavioural equivalence that arises in the pi-calculus (as in many other process algebras) is that of `strong bisimilarity.' Two processes are bisimilar if they can be related by a bisimulation, i.e. if they can both perform the same actions and essentially mimic the transitions of each other. However bisimilarity is not a congruence since it is not preserved by the input prefix, and so this motivates the introduction of `strong congruence'. Two agents are strongly congruent if they are bisimilar for all substitutions. The author proves that strong congruence is the largest congruence in bisimilarity. Of modern recent interest is the notion of `barbed' congruence, which is discussed by the author in this article and which involves the inability of an observer to find out if an action is enabled on a given channel. This is a `barbed bisimulation' and two agents are `barbed congruent' if they are related by a barbed bisimulation for all contexts.

The operational semantics of the pi-calculus is given by a labeled transition system. The transitions are labeled by a collection of actions: the internal action, the free output actions, and the input actions, and no actions are possible for a restricted name as subject. But there is also a notion of `bound output' action that the author explains in some detail, where a local name can be transmitted and its scope extended to the recipient.