Mathematical Foundations of Automata Theory Jean-Éric Pin

These notes form the core of a future book on the algebraic foundations of automata theory. This book is still incomplete, but the first eleven chapters now form a relatively coherent material, covering roughly the topics described below. The early years of automata theory Kleene’s theorem [49] is usually considered as the starting point of automata theory. It shows that the class of recognisable languages (that is, recognised by finite automata), coincides with the class of rational languages, which are given by rational expressions. Rational expressions can be thought of as a generalisation of polynomials involving three operations: union (which plays the role of addition), product and the star operation. It was quickly observed that these essentially combinatorial definitions can be interpreted in a very rich way in algebraic and logical terms. Automata over infinite words were introduced by Büchi in the early 1960s to solve decidability questions in first-order and monadic second-order logic of one successor. Investigating two-successor logic