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.
