zbMATH — the first resource for mathematics

The linear time – branching time spectrum. I: The semantics of concrete, sequential processes. (English) Zbl 1035.68073
Bergstra, Jan A. (ed.) et al., Handbook of process algebra. Amsterdam: North-Holland/ Elsevier (ISBN 0-444-82830-3). 3-99 (2001).
The paper forms a chapter of the Handbook of Process Algebra and extends the technical report (CS-R9029, CWI Amsterdam) with research on linear time versus branching time.
On 97 pages the author descibes, compares and axiomatizes various semantics or sequential processes and thereby sharpens their classification. The author uses a uniform algebraic framework for the presentation. A selection of equivalences are presented, however, parallelism and/or silent moves or invisible actions are not dealt with in this work.
The linear time branching time spectrum for 12 process semantics is partially ordered by the relation ‘makes as least as many identifications as’. The completeness of this comparison and its uniform treatment are a valuable contribution to the sequential part within the larger field of ‘comparative concurrent processes’.
The titles of the 23 sections of this paper shall serve as short information of its contents:
Introduction; 1. Labelled transition systems and process graphs; 2. Trace semantics; 3. Complete trace semantics; 4. Failures semantics; 5. Failure trace semantics; 6. Ready trace semantics; 7. Readiness semantics and possible-future semantics; 8. Simulation semantics; 9. Ready simulation semantics; 10. Reactive versus generative testing scenarios; 11. 2-nested simulation semantics; 12. Bisimulation semantics; 13. Tree semantics; 14. Possible world semantics; 15. Summary; 16. Deterministic and saturated processes; 17. Complete axiomatization; 18. Criteria for selecting a semantics for particular applications; 19. Distinguishing deadlock and successful termination; Concluding remarks; References; Subject index.
For the entire collection see [Zbl 0971.00006].

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q55 Semantics in the theory of computing