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

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.

List 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.

Summary

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.

Additional text

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)

Report

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)

Product details

• Authors: Benedikt Bollig
• Publisher: Springer, Berlin
• Languages: English
• Product format: Paperback / Softback
• Released: 12.10.2010
• EAN: 9783642069475
• ISBN: 978-3-642-06947-5
• No. of pages: 181
• Dimensions: 155 mm x 10 mm x 235 mm
• Weight: 301 g
• Illustrations: IX, 181 p.
• Subjects: Natural sciences, medicine, IT, technology > IT, data processing > IT; B, Algorithmen und Datenstrukturen, Software Engineering, Algorithms, Netzwerk-Hardware, computer science, Theory of Computation, Computer Communication Networks, Information Systems and Communication Service, Computers, Algorithms & data structures, Mathematical theory of computation, Algorithm Analysis and Problem Complexity, Mathematical logic, Mathematical Logic and Foundations, Mathematical Logic and Formal Languages, Database Management System, Computer networking & communications, Computation by Abstract Devices, Formal Languages and Automata Theory