Combinatorics on Words (Sanojen kombinatoriikka), 10 op
mate5075
Spring 2010 (periods 3 and 4)
Lecturer Juhani Karhumäki, e-mail juhani.karhumaki[at]utu.fi
Contents: A word is a finite or infinite sequence of symbols (from a finite set). In this course we consider simple, as well as more advanced, combinatorial problems of words. For example, when two words commute, or how long words exist without containing a repetition of a certain type (like a square). Also some more algebraic properties of words are considered, results have applications in many fields of discrete mathematics and theoretical computer science.
Preliminary knowledge: Basics on algorithms and combinatorics are needed, and on automata is useful.
Performance: Lectures (56 h), exercises (28 h), examination.
Grading: 0 - 5
Recommended literature:
- Lecture notes ;
- M.Lothaire: Combinatorics on words, Addison-Wesley, 1983;
- C. Choffrut and J. Karhumäki: Combinatorics of words, in Handbook of Formal Languages Vol. 1 (G. Rozenberg and A. Salomaa, Eds.), pp. 329-438. Springer, Berlin 1997;
- M. Lothaire: Algebraic Combinatorics on Words (Encyclopedia of Mathematics and its Applications, vol. 90).Cambridge University Press 2002.
Level: Advanced studies
The course will be lectured in English.
Exercises
19.1.2010 , 26.1.2010 , 2.2.2010 , 9.2.2010 , 18.2.2010 , 19.2.2010 , 23.2.2010 , 9.3.2010 , 16.3.2010 , 23.3.2010 , 9.4.2010 , 16.4.2010