Read more
Informationen zum Autor Javier Esparza is Professor and Chair of Foundations of Software Reliability and Theoretical Computer Science at the Technical University of Munich and coauthor of Free Choice Petri Nets and Unfoldings: A Partial-Order Approach to Model Checking. Michael Blondin is Associate Professor of Computer Science at the Université de Sherbrooke. Klappentext "The book presents automata theory from a fresh viewpoint inspired by its main modern application: program verification"-- Zusammenfassung A comprehensive introduction to automata theory that uses the novel approach of viewing automata as data structures. This textbook presents automata theory from a fresh viewpoint inspired by its main modern application, program verification, where automata are viewed as data structures for the algorithmic manipulation of sets and relations. This novel “automata as data structures” paradigm makes holistic connections between automata theory and other areas of computer science not covered in traditional texts, linking the study of algorithms and data structures with that of the theory of formal languages and computability. Esparza and Blondin provide incisive overviews of core concepts along with illustrated examples and exercises that facilitate quick comprehension of rigorous material. Uses novel “automata as data structures” approach Algorithm approach ideal for programmers looking to broaden their skill set and researchers in automata theory and formal verification The first introduction to automata on infinite words that does not assume prior knowledge of finite automata Suitable for both undergraduate and graduate students Thorough, engaging presentation of concepts balances description, examples, and theoretical results Extensive illustrations, exercises, and solutions deepen comprehension Inhaltsverzeichnis Preface xiii 0 Overview 1 I Automata on Finite Words 1 Automata Classes and Conversions 9 2 Minimization and Reduction 49 3 Operations on Sets: Implementations 75 4 Application 1: Pattern Matching 101 5 Operations on Relations: Implementations 113 6 Finite Universes and Decision Diagrams 131 7 Application II: Verification 163 8 Automata and Logic 193 9 Application III: Presburger Arithmetic 229 II Automata on Infinite Words 10 Classes of Automata and Conversions 247 11 Boolean Operations: Implementations 289 12 Emptiness Check: Implementations 313 13 Application I: Verification and Temporal Logic 341 14 Application II: MSO Logics on Words and Linear Arithmetic 365 Solutions 377 Bibliographic Notes 523 Bibliography 531 Index 539...
