Groups, languages, and automata

Anisimov introduced the idea of studying the Word Problem through formal language theory by asking the following question: what can be said about a group if its Word Problem is a regular or context-free language in the classical sense of language theory? Anisimov himself proved that a finitely generated group has a regular Word Problem if and only if the group is finite. Later, Muller and Schupp showed that a finitely generated group has a context-free Word Problem if and only if the group is virtually free.

These results sparked considerable interest in the application of automata theory and formal languages to the study of group properties.

The objective of this course is twofold. On the one hand, we introduce the notions of regular, context-free, and recursively enumerable languages, along with the corresponding classes of automata: finite-state automata, pushdown automata, and Turing machines. On the other hand, we discuss properties of finitely generated groups and their associated Cayley graphs. We then consider the Word Problem of a finitely generated group as a formal language. We prove the characterizations of Anisimov and Muller - Schupp and, more generally, explore other surprising connections between automata, formal languages, and group theory.

Schedule:

May 7th - 10.30-13.00
May 11th - 10.30-13.00
May 18th - 10.30-13.00
May 25th - 10.30-13.00

You can find all the material here.

Microsoft teams link: Generale | Groups, Languages, and Automata

References:

G. Baumslag, Topics in combinatorial group theory - Lectures in Mathematics ETH Zürich, Birkhäuser Verlag, Basel (1993).
L. Bartholdi, R.I. Grigorchuk, and Z. Sunik, Branch groups - Handbook of Algebra, Volume 3, North-Holland 989-1112 (2003).
H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi - Tree Automata Techniques and Applications (2007).
R.W. Floyd, and R. Beigel, The Language of Machines: an Introduction to Computability and Formal Languages - Computer Science Press, New York (1994).
P. de la Harpe, Topics in Geometric Group Theory - Chicago Lectures in Mathematics (2000).
D. Holt, S. Rees, and C. E. Röver, Groups, Languages, and Automata - London Mathematical Society Student Texts 88 (2017).
J.E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation - Addison-Wesley Longman Publishing Co., Inc. (2006).
V. Nekrashevych, Self-similar groups - Mathematical Surveys and Monographs, 117, American Mathematical Society (2005).

Page updated

Google Sites

Report abuse