Formal Models of Communicating Systems

Languages, Automata, and Monadic Second-Order Logic

Benedikt Bollig (Autor)

Buch | Hardcover

IX, 181 Seiten

2006
Springer Berlin (Verlag)
9783540329220 (ISBN)

Artikel merken

lt;p>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.

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.

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)

Erscheint lt. Verlag	24.7.2006
Zusatzinfo	IX, 181 p.
Verlagsort	Berlin
Sprache	englisch
Maße	155 x 235 mm
Gewicht	405 g
Themenwelt	Mathematik / Informatik ► Informatik ► Theorie / Studium
Schlagworte	Algorithm analysis and problem complexity • Asynchronous cellular automata • Automata • Automata Theory • communicating systems • Distributed Systems • Finite Automata • Finite-State Machines • formal methods • Graphs • Kommunikationssystem • Logic • Mazurkiewicz traces • message sequence charts • Modeling • Software engineering
ISBN-13	9783540329220 / 9783540329220
Zustand	Neuware