The material in this book is located at the intersection of automata theory, logic, computational complexity and semigroup theory. The first part of this book is devoted to the algebraic characterization of regular languages defined in many different logical theories. in monadic second-order language, and McNaughton and Papert in the first-order logic and star-free languages, as well as more recent developments that have not been treated much in book form. The second part presents the recent connection found between the theory of algebraic automata and complexity theory of small-depth circuits.