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

by Benedikt Bollig

Overview

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.

Product Details

ISBN-13:	9783540329220
Publisher:	Springer Berlin Heidelberg
Publication date:	10/10/2006
Edition description:	2006
Pages:	181
Product dimensions:	6.10(w) x 9.25(h) x 0.02(d)

Table of Contents

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.

Editorial Reviews

From the reviews:

"The book deals with one essential problem of communication systems, namely formal description of prools 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)

From the Publisher