Formal Models of Communicating Systems
Languages, Automata, and Monadic Second-Order Logic

by Benedikt Bollig

Springer Verlag, July, 2006
181 Pages
ISBN: 3540329226
Link to Springer Webpage of the book

From the reviews:

"The book deals with one essential problem of communication systems, namely formal description of protocols and systems and verification of correctness of their operation. ... The book, due to clear definitions, well proved theorems and a number of illustrative examples, can be advised as a valuable source of knowledge for graduate mathematics and computer science students." (Jozef Wozniak, Zentralblatt MATH, Vol. 1107 (9), 2007)



This book studies the relationship between automata and monadic second-order logic, focusing on classes of automata that describe the concurrent behavior of distributed systems.

It provides a unifying theory of communicating automata and their logical properties. Based on Hanf's Theorem and Thomas's graph acceptors, it develops a result that allows us to characterize many popular models of distributed computation in terms of the existential fragment of monadic second-order logic. In particular, the book covers finite automata, asynchronous (cellular) automata, communicating finite-state machines, and lossy channel systems. Model behavior is described using graphs and partial orders, leading to the notions of Mazurkiewicz traces, message sequence charts, and live sequence charts.

This book is suitable for senior undergraduate and graduate courses on advanced automata theory, concurrency and communication issues. It can also be used as a reference by researchers concerned with the formal modeling of concurrent systems. Some knowledge of automata theory is a prerequisite. Numerous exercises, chapter summaries, and suggested reading allow for self-study, while the book is supported with a website containing course material and solutions.

181 pages, with Exercises, Bibliographical Remarks, 72 Figures, and 6 Tables

Table of Contents:
  1. Introduction
  2. Preliminaries
  3. Graphs, Logics, and Graph Acceptors
  4. Words and Finite Automata
  5. Dags and Asynchronous Cellular Automata
  6. Mazurkiewicz Traces and Asynchronous Automata
  7. Message Sequence Charts
  8. Communicating Finite-State Machines
  9. Beyond Implementability
          References, Symbols and Notation, Index

Benedikt Bollig
Last modified: Sun Oct 4 20:43:35 CEST 2009