×

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.

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.
PDFBibTeX XMLCite