An Invitation to Algorithmic Automata Theory

Algorithms and Automata Theory are often regarded as two separate subfields of theoretical computer science. Nevertheless, interesting results can be obtained when advanced techniques from one of the fields are used to attack problems in the other. 

 In this lecture, I will survey several results that lie at the intersection of automata theory and algorithms.

 I will start by discussing some early developments in the interplay between the two fields.

Subsequently, I will describe several examples of recent algorithmic results that have been obtained using automata-theoretic techniques. Among these results are new parameterized algorithms for problems of relevance to graph theory, term rewriting systems theory, and automated deduction.

Finally, I will describe some new research directions in automata theory that will be used to establish unexplored connections between parameterized complexity theory and fields such as automated deduction and symbolic constraint satisfaction. 

This will be a non-technical lecture, where definitions, statements, and examples will be presented in an intuitive way.