Formal Models of Communicating Systems

Precise characterizations of automata models in terms of descriptive logic formalisms Software engineers can use fragments of monadic second-order logic to specify desired system behaviors First monograph dealing with the relationship between automata and monadic second-order logic Focuses on classes of automata that describe the concurrent behavior of distributed systems Includes supplementary material: sn.pub/extras

Klappentext

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 characterization of many popular models of distributed computation in terms of the existential fragment of monadic second-order logic.

Inhalt
Preliminaries.- Graphs, Logics, and Graph Acceptors.- Words and Finite Automata.- Dags and Asynchronous Cellular Automata.- Mazurkiewicz Traces and Asynchronous Automata.- Message Sequence Charts.- Communicating Finite-State Machines.- Beyond Implementability.