LOGIC, SEMIGROUPS AND AUTOMATA ON WORDS

This is a survey article on the connections between the ''sequential c alculus'' of Buchi, a system which allows to formalize properties of w ords, and the theory of automata. In the sequential calculus, there is a predicate for each letter and the unique extra non logical predicat e is the relation symbol <, which is interpreted as the usual order on the integers. Several famous classes have been classified within this logic. We briefly review the main results concerning second order, wh ich covers classes like PH, NP, P etc., and then study in more detail the results concerning the monadic second-order and first-order logic. In particular, we survey the results and fascinating open problems de aling with the first-order quantifier hierarchy. We also discuss the f irst-order logic of one successor and the linear temporal logic. There are in fact three levels of results, since these logics can be interp reted on finite words, infinite words or bi-infinite words. The paper is self-contained. In particular, the necessary background on automata and finite semigroups is presented in a long introductory section, wh ich includes some very recent results on the algebraic theory of infin ite words.