Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0816.68086
Straubing, Howard
Finite automata, formal logic, and circuit complexity. (English)
[B] Progress in Theoretical Computer Science. Basel: Birkhäuser. xii, 226 p. DM 88.00; öS 686.40; sFr 78.00; \sterling 35.00 /hc (1994). ISBN 0-8176-3719-2

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.
[G.Asser (Greifswald)]

MSC 2000:: *68Q70 Algebraic theory of automata
68-02 Research monographs (computer science)
03D05 Automata theory in connection with logical questions
18B20 Categories of automata, etc.
20M35 Semigroups in automata theory, linguistics, etc.

Keywords: automata theory; semigroup theory; computational complexity

Cited in: Zbl 0874.68218

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]