Handbook of Automata Theory Volume I Theoretical Foundations

The Handbook of Automata Theory has its origins in the research programme AutoMathA
(Automata: from Mathematics to Applications, 2005–2010), a multidisciplinary
programme of the European Science Foundation at the crossroads of mathematics,
theoretical computer science, and applications. It is designed to provide a broad
audience of researchers and students in mathematics and computer science with a comprehensive
overview of research in automata theory.
Automata theory is one of the longest established areas in computer science. It
was born over sixty years ago, with the seminal work of Kleene, who first formalised
the early attempts of McCulloch and Pitts, and was originally motivated by the study
of neural networks. For many years, its main applications have been computer design,
compilation of programming languages, and pattern matching. But over the last twenty
years, applications of automata theory have considerably diversified, and now include
verification methods to cope with such emerging technical needs as network security,
mobile intelligent devices, and high performance computing.
At the same time, the mathematical foundations of automata theory rely on more
and more advanced parts of mathematics. While only elementary graph theory and
combinatorics were required in the early sixties, new tools from non-commutative
algebra (semigroups, semirings and formal power series), logic, probability theory, and
symbolic dynamics have been successively introduced, and the latest developments
borrow ideas from topology and geometry.
It was time to gather these mathematical advances and their numerous applications
in a reference book. The Handbook of Automata Theory is intended to serve this
purpose. It comprises thirty-nine chapters, presented in two volumes:
Volume I: Theoretical foundations
Volume II: Automata in mathematics and selected applications