 | | |
| MATH0470-1 | Combinatorics on words
|
|
| Duration : | 30h Th, 10h Pr, 20h Mon. WS |
|
| Number of credits : |
|
|
| Lecturer : | Michel Rigo |
|
Language(s) of instruction :
|
| French language |
|
Organisation and examination :
|
| All year long |
|
Course contents :
|
| Combinatorics is a branch of mathematics dealing with the "configurations" of a "discrete" set (in general finite). One usually looks for counting or efficiently enumerating elements of such a set, for the (possibly algebraic) structure of the set or also for its extremal properties (maximal elements, ...). Of course combinatorics on words is interested with (finite or infinite) words, i.e., sequences of symbols or letters belonging to a finite set. To illustrate this concept, let us state a typical result in words combinatorics, the so-called Morse-Hedlund's theorem: an infinite word indexed by N is ultimately periodic if and only if the function p(n) counting the number of factors (or subwords) of length n appearing in this word is bounded from above by a constant. |
|
Learning outcomes of the course :
|
| The aim of this course is to prepare students to the study of some actual research questions in discrete mathematics or theoretical computer science. Problems arising from the representation of numbers and the recognizability (by finite automata) of the corresponding sets are used to introduce concepts from combinatorics on words. The following topics can be considered (the list is not exhaustive): integer base number system and recognizable sets of integers (bounded gaps, syndeticity, ...), Cobham's theorems, p-automatic sequences (fiber, kernel, Prouhet's problem, ...), morphic words (i.e., sequences generated by iterated morphisms), normalization, sets definable in extended Presburger arithmetic, introduction to beta-numeration (beta-shift, Bertrand-Schmidt theorem, Parry numbers, ...), linear number systems (theorems of Shallit, Hollander, Hansel, ...), Pisot numbers and associated number systems (Bertrand systems), return words, sturmian sequences and continued fractions, links with discrete geometry, ...
At the end of this course, the student will be able to work autonomously as a researcher in mathematics. He/she will be able to summarize an actual topic of research, to produce a corresponding document (article and/or talk) and to propose further investigations. |
|
Prerequisites and co-requisites/ Recommended optional programme components :
|
| Basic knowledge in automata theory and formal languages theory like the one from INFO0213-2 "Automata and formal languages theory" is required. Knowledge from graph theory and computability/complexity theory and basic knowledge from number theory can be useful but are not compulsory. |
|
Planned learning activities and teaching methods :
|
| Reading research papers and text books, participating in seminars, tailored courses. |
|
Mode of delivery (face-to-face ; distance-learning) :
|
| This course, preparing to research, needs an active participation from the student. To learn concepts at the best, personal work and oral presentations given by the students will be sought. |
|
Recommended or required readings :
|
| Reference books :
- M. Rigo, Formal languages, automata and numeration systems, vol. 1, Introduction to combinatorics on words, ISTE-Wiley (2014).
- M. Rigo, Formal languages, automata and numeration systems, vol. 1, Applications to recognizability and decidability, ISTE-Wiley (2014).
This course mostly uses selected scientific research papers or books. As usual, scientific literature is in English. Some examples:
- M. Lothaire, Combinatorics on words, Cambridge University Press (1997).
- M. Lothaire, Algebraic combinatorics on words, Cambridge University Press (2002).
- V. Berthé, M. Rigo (Eds.), Combinatorics, Automata and Number Theory, Cambridge University Press (2010).
- J. Sakarovitch, Elements de théorie des automates, Vuibert (2003)
- V. Bruyère, G. Hansel, C. Michaux, R. Villemaire, Logic and p-recognizable sets of integers, Bull. Belg. Math. Soc. (1994).
- J.-P. Allouche, J. Shallit, Automatic sequences, Theory and applications, Cambridge University Press (2003).
- Thomas S. Ferguson, Game Theory, UCLA.
- J. Shallit, A second course in formal languages and automata theory, Cambridge University Press (2008).
- E. Bach, J. Shallit,Algorithmic Number Theory, volume 1: efficient algorithms, MIT Press (1996).
- A. de Luca, S. Varricchio, Finiteness and Regularity in Semigroups and Formal Languages, Springer (1999).
|
|
Assessment methods and criteria :
|
| Personal works realized all along the year (oral presentations, discussions, reports, solving exercises, ...) make the major part of the final mark. The final examination is made of a presentation (on a subject given in advance) and an oral examination on a limited part of the material presented during the year and its direct applications (student may also be asked to solve a small exercise on the blackboard). |
|
Work placement(s) :
|
| |
|
Organizational remarks :
|
| |
|
Contacts :
|
| M. Rigo
Institute of Mathematics (B37) - Grande Traverse 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be |
|
|
| |
