Bridges between Algebraic Automata Theory and Complexity Theory.
Pascal Tesson, Denis Thérien · 2006
The algebraic theory of finite automata has been one of the most successful tools to study and classify regular languages. These very same tools can in fact be used to understand more powerful models of computation and we discuss here the impact that semigroup theory can have in computational complexity. 1