Introduction to Concurrency Theory | springerprofessional.de

Springer Professional

nach oben

2015 | Buch

Kapitel lesen Erstes Kapitel lesen

Introduction to Concurrency Theory

Transition Systems and CCS

verfasst von: Roberto Gorrieri, Cristian Versari

Verlag: Springer International Publishing

Buchreihe : Texts in Theoretical Computer Science. An EATCS Series

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book presents the fundamentals of concurrency theory with clarity and rigor. The authors start with the semantic structure, namely labelled transition systems, which provides us with the means and the tools to express processes, to compose them, and to prove properties they enjoy. The rest of the book relies on Milner's Calculus of Communicating Systems, tailored versions of which are used to study various notions of equality between systems, and to investigate in detail the expressive power of the models considered.

The authors proceed from very basic results to increasingly complex issues, with many examples and exercises that help to reveal the many subtleties of the topic. The book is suitable for advanced undergraduate and graduate students in computer science and engineering, and scientists engaged with theories of concurrency.

Anzeige

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract

This introductory chapter outlines the main motivations for the study of concurrency theory and the differences with respect to the theory of sequential computation. It also reports the structure of the book and how to use it. Finally, some background material is briefly surveyed.

Roberto Gorrieri, Cristian Versari

Chapter 2. Transition Systems and Behavioral Equivalences

Abstract

Transition systems are introduced as a suitable semantic model of reactive systems. Some notions of behavioral equivalence are discussed, such as isomorphism equivalence, trace equivalence, simulation equivalence and bisimulation equivalence. Internal, unobservable actions are also considered and many behavioral equivalences are suitably adapted for this case.

Roberto Gorrieri, Cristian Versari

Chapter 3. CCS: A Calculus of Communicating Systems

Abstract

The process calculus CCS for describing reactive systems is introduced. Its syntax is defined, as well as its operational semantics in terms of labeled transition systems. Some subcalculi are singled out that possess some specific interesting expressiveness properties. It is shown that CCS is Turing-complete by offering an encoding of Counter Machines into CCS. As a byproduct, all the behavioral equivalences of interest are undecidable over the class of CCS processes, even if they are decidable over some subcalculi.

Roberto Gorrieri, Cristian Versari

Chapter 4. Algebraic Laws, Congruences and Axiomatizations

Abstract

Behavioral equivalences, in particular those based on bisimulation, are shown to possess interesting algebraic laws. Moreover, we discuss which of them are congruences with respect to the CCS operators. Finally, behavioral congruences are axiomatized over finite CCS, and also finitely with the use of two auxiliary operators.

Roberto Gorrieri, Cristian Versari

Chapter 5. Additional Operators

Abstract

Some additional operators are investigated: the internal choice operator and the hiding one of CSP, the relabeling operator occurring in early versions of CCS, the sequential composition operator and the iteration operator of ACP, the replication operator of the π-calculus, and, finally, CSP parallel composition with multiway synchronization. The main aim of this chapter is to show that most of them are encodable into CCS, hence proving that CCS is reasonably expressive.

Roberto Gorrieri, Cristian Versari

Chapter 6. Multi-CCS

Abstract

We present Multi-CCS, an extension to CCS obtained by introducing one additional operator of prefixing, \(\underline{\alpha}.p\), called strong prefixing (as opposed to normal prefixing, \(\mu.p\)), with the capability of expressing atomic sequences of actions and, together with parallel composition, also multi-party synchronization.

Roberto Gorrieri, Cristian Versari

Backmatter

Titel: Introduction to Concurrency Theory
verfasst von: Roberto Gorrieri
Cristian Versari
Copyright-Jahr: 2015
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-21491-7
Print ISBN: 978-3-319-21490-0
DOI: https://doi.org/10.1007/978-3-319-21491-7

Premium Partner