Straubing, Howard Finite automata, formal logic, and circuit complexity. (English) Zbl 0816.68086 Progress in Theoretical Computer Science. Basel: Birkhäuser. xii, 226 p. DM 88.00; öS 686.40; sFr 78.00; £35.00 /hc (1994). From author’s preface: “The present book, intended for researchers and advanced students in theoretical computer science and mathematics, is situated at the juncture of automata theory, logic, semigroup theory and computational complexity. The first seven chapters are devoted to the algebraic characterization of the regular languages definable in many different logical theories, obtained by verying both the kinds of quantification and the atomic formulas that are admitted. This includes the results of Büchi and of McNaughton-Papert, as well as more recent developments that are scattered throughout research journals and conference proceedings. Chapter VIII is a brief account of complexity theory of small-depth families of boolean circuits. In Chapter IX it is shown that questions about the structure of complexity classes of small- depth circuits are precisely equivalent to questions about the definability of regular languages in various versions of first-order logic.” The book gives a good coherent treatment of the described area. Reviewer: G.Asser (Greifswald) Cited in 2 ReviewsCited in 134 Documents MSC: 68Q70 Algebraic theory of languages and automata 68-02 Research exposition (monographs, survey articles) pertaining to computer science 03D05 Automata and formal grammars in connection with logical questions 18B20 Categories of machines, automata 20M35 Semigroups in automata theory, linguistics, etc. Keywords:automata theory; semigroup theory; computational complexity PDFBibTeX XMLCite \textit{H. Straubing}, Finite automata, formal logic, and circuit complexity. Basel: Birkhäuser (1994; Zbl 0816.68086)