Book Layout
The 18 chapters of this handbook were contributed by 32 authors from 12 countries.
The first six chapters introduce the fundamentals of automata theory and some widely used automata, including transducers, tree automata, quantum automata and timed automata. Regular expressions are part of automata theory and provide a concise and flexible means for matching strings of text. Transducers are a sort of state machines that transform an input string to an output string. Tree automata deal with tree structures that are one of the most basic and widely used data structures. Timed automata are suitable for real-time systems modeling and analysis. Quantum automata are a powerful tool to capture various important features of quantum processors.
The next two chapters present algorithms for the minimization and incremental construction of finite automata.
Chapter 9 introduces Esterel, an automata-based synchronous programming language that has been widely applied to embedded system software development.
A few distinguishing applications of automata are showcased in Chapters 10-14, including regular path queries on graph-structured data, timed automata in model checking security protocols, pattern-matching, complier design and XML processing.
Other finite state based modeling approaches and their applications are presented in Chapters 15-18. Petri nets are a high-level model for event-driven systems. The reachability graph of a Petri net is a state transition system. Statecharts, like Petri nets, provide a practical and expressive visual formalism to describe reactive systems. Temporal logic is suitable for system functional property specification and its application has been promoted by the development of model checking tools. UML state machine diagrams are an object-based variation of Harel’s statecharts with the addition of activity diagram notations.