The study of the connections between mathematical automata and for mal logic is as old as
theoretical computer science itself. In the founding paper of the subject published in 1936
Turing showed how to describe the behavior of a universal computing machine with a formula of
first order predicate logic and thereby concluded that there is no algorithm for deciding the
validity of sentences in this logic. Research on the log ical aspects of the theory of
finite-state automata which is the subject of this book began in the early 1960's with the
work of J. Richard Biichi on monadic second-order logic. Biichi's investigations were extended
in several directions. One of these explored by McNaughton and Papert in their 1971 monograph
Counter-free Automata was the characterization of automata that admit first-order behavioral
descriptions in terms of the semigroup theoretic approach to automata that had recently been
developed in the work of Krohn and Rhodes and of Schiitzenberger. In the more than twenty years
that have passed since the appearance of McNaughton and Papert's book the underlying semigroup
theory has grown enor mously permitting a considerable extension of their results. During the
same period however fundamental investigations in the theory of finite automata by and large
fell out of fashion in the theoretical com puter science community which moved to other
concerns.
