Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency: School/Workshop, Noordwijkerhout, The Netherlands, May 30 - June 3, 1988 (Lecture Notes in Computer Science)

"This volume is based on the "School/Workshop on Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency" organized by the editors and held in the period May 30-June 3, 1988 at Noordwijkerhout, The Netherlands. The School/Workshop was an activity of the project REX - Research and Education in Concurrent Systems. The volume contains tutorials and research contributions to the three approaches - linear time, - branching time, and - partial order in semantics and proof theory of concurrent programs by the main specialists in this field. It promotes an in-depth understanding of the relative merits and disadvantages of these three approaches. An introduction to the recent literature on the subject is provided by the invited research contributions.''--Publisher's website. Modelling the behaviour of concurrent and distributed systems has grown into one of the most challenging and vigorous research areas within theoretical computer science. The last decade has seen the emergence of three independent approaches to this problem, some of them capturing differences between systems that others ignore. The first one models a system by describing its execution runs, the second one by analysing the execution trees, and the third one models a system by describing the (in)dependencies and choices between the various events that may occur. Paradigmatic for these approaches are semantic domains with linear or branching elements, linear time and branching time temporal logic, and net theory. Although it seems that the more features a system captures the better, if one wants some measure of abstractness and parsimony, some of such features may be too detailed for a given level of description. This volume reviews these intrinsically different approaches and evaluates their relative advantages. It is based on the "School/Workshop On Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency" organized by the editors and held in the period May 30 - June 3, 1988 at Noordwijkerhout, The Netherlands. The School/Workshop was an activity of the project REX - Research and Education in Concurrent Systems sponsored by the Netherlands NFI (Nationale Faciliteit Informatica) Programme. The meeting was organized under auspices of the EATCS and was furthermore supported by the Centre for Mathematics and Computer Science, the University of Leiden, and the Eindhoven University of Technology Time, logic and computation....Pages 1-49 Process theory based on bisimulation semantics....Pages 50-122 Branching time temporal logic....Pages 123-172 Observing processes....Pages 173-200 The anchored version of the temporal framework....Pages 201-284 Basic notions of trace theory....Pages 285-363 An introduction to event structures....Pages 364-397 A logic for the description of behaviours and properties of concurrent systems....Pages 398-410 Permutation of transitions: An event structure semantics for CCS and SCCS....Pages 411-427 Expressibility results for linear-time and branching-time logics....Pages 428-437 Partial orderings descriptions and observations of nondeterministic concurrent processes....Pages 438-466 Modeling concurrency by partial orders and nonlinear transition systems....Pages 467-488 An efficient verification method for parallel and distributed programs....Pages 489-507 A logic for distributed transition systems....Pages 508-522 Fully abstract models for a process language with refinement....Pages 523-548 Strong bisimilarity on nets: A new concept for comparing net semantics....Pages 549-573 Nets of processes and data flow....Pages 574-602 Towards a temporal logic for causality and choice in distributed systems....Pages 603-627 Correctness and full abstraction of metric semantics for concurrency....Pages 628-659 Temporal logics for CCS....Pages 660-672 Behavioural presentations....Pages 673-689 Computation tree logic and regular ω-languages....Pages 690-713