zbMATH — the first resource for mathematics

Communicating sequential processes. (English) Zbl 0637.68007
Prentice-Hall International Series in Computer Science. Englewood Cliffs, New Jersey etc.: Prentice-Hall International. 256 p.; $ 57.95; £31.95 (1985).
This book provides a theoretical treatment of computing in a very general sense. The treatment is based on mathematics rather than on any real computing hardware. On the other hand, mathematical terms chosen to present the behaviour of machines or languages or programs (processes in short) are so adequate that it is possible to come as close to actual computing devices as one only wishes.
The mathematically precise treatment of processes is based on a rather simple concept of a device responding to events which happen in the device’s environment. The device may be elementary, responding to only a few possible events, or it may be a complex combination of many different devices which respond to a variety of events. Responses may also become events to still other devices, so that communication between devices may be considered.
If a device responds to an event always the same way, it is deterministic. If there is a set of possible responses, it is non- deterministic. If there is a number of devices responding to the same events, we have a parallel composition of devices. The book presents a number of possible compositions each defined as an operator with a precise meaning and a set of laws governing its application. Apart from usual compositions of processes like non-deterministic choice, fork, join, etc., the book also gives mathematical definitions of compositions that have not been yet treated theoretically, like one process interrupting another, one process replacing another after a catastrophe, etc.
The behaviour (actual or anticipated) of a device may be described by its trace - a sequence of events in which the device has been engaged. Traces are also mathematical entities that may undergo transformations, reductions, substitutions, and other usual mathematical manipulations if only relevant laws are obeyed. Mathematics of the traces is crucial in establishing whether a particular design of a process structure will behave as expected, or if it contains errors that may lead to infinite loops, deadlocks, and other disasters. On one hand, the author shows how to apply mathematics to programming, on the other, he develops a new branch of mathematics - mathematics of communicating sequential processes.
Apart from theoretical, the book has also its practical aspect. Every presented process structuring concept is also illustrated by a Lisp-like implementation which can actually be tested on a real computer, and which may help in comprehension of formal definitions.
Reviewer: J.Olszewski

68-02 Research exposition (monographs, survey articles) pertaining to computer science
68Q65 Abstract data types; algebraic specification
68N01 General topics in the theory of software
68Q45 Formal languages and automata