Fundamentals of Computing and Discrete Mathematics

Dominique Perrin

Université Paris-Est Marne-la-Vallée - France

January 2011

Distinguished Lecture Colloquium

Combinatorics on Words and Group Theory

There is a well-established connection between groups and words which is linked with the work of Dehn, Magnus and Nielsen. Since then, a broad set of results have been obtained which interconnect automata and combinatorics on words with groups. This has stimulated research in combinatorics on words, in particular concerning unavoidable regularities in words. On the other hand, the theory of groups has used automata in developing for example the notion of automatic groups or the notion of Stallings automaton. In this talk, I will present an overview of the relations between automata, words and groups. In particular, I will present new results which connect Sturmian words to finite groups (joint work with Jean Berstel, Clelia De Felice and Giuseppina Rindone).

TUCS Short Course

Combinatorics on Words and Group Theory

The aim of these lectures is to describe results which relate automata, codes and groups. The basic results are presented in the volume “Codes and Automata” by Jean Berstel, Christophe Reutenauer and myself (Cambridge, 2010).

Lectures schedule:
  • Bifix codes and Sturmian words.
  • Sturmian basis of a free group.
  • Syntactic groups.
Last modified: Tuesday October 07, 2014