Theory and Application of Büchi Automata

Model checking is a method used for testing the reliability of a system. The automata-theoretic approach to model checking involves expressing systems in terms of finite state automata, and using algorithms that automatically determine the satisfiability of logic specifications for these systems.Classical automata theory stops short of this task because of its inadequateness to express real-time concurrent systems. This is where the theory of automata on infinite strings comes into play. Büchi automata belong to a class of automata that have the capability of recognizing infinite inputs.This book studies Büchi automata, their closure properties and their application in model checking. It discusses the use of Linear Temporal Logic (LTL) and its translation into Büchi automata. By reporting on experiments using the LTL2BA program, the book provides a comparative analysis of the quality of translations based on certain performance criteria, such as LTL formula simplification and on-the-fly automata simplification .