 | |
| MATH0470-1 | Combinatorics on words
 |
|
| Duration : | 30h Th, 10h Pr, 20h Mon. WS |
|
| Credits/ECTS : |
|
|
| Holder(s) : | Michel Rigo |
|
| Language : | French language |
|
| 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. |
|
| Course objective : | 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, ... |
|
| Prerequisites : | 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. |
|
| Organization : | 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. |
|
| Written notes : | This course mostly uses selected scientific research papers or reference books. As usual, scientific literature is in English. |
|
| Assessment : | The final examination has a written part and an oral one. The latter is devoted to the theory but also direct applications of the theory (student may be asked to solve a small exercise on the blackboard). Note that personal work made during the year (oral presentations, reports, ...) are taken into account for the final mark. |
|
| 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 |
|
|
| |
