Duration
30h Th, 20h Pr
Number of credits
| Master in mathematics (120 ECTS) (Odd years, organized in 2023-2024) | 8 crédits |
Lecturer
Language(s) of instruction
English language
Organisation and examination
Teaching in the first semester, review in January
Schedule
Units courses prerequisite and corequisite
Prerequisite or corequisite units are presented within each program
Learning unit 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 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 counting the number of factors (or subwords) of length n appearing in this word is bounded from above by a constant. Topics: periodicity, complexity function, Sturmian words, automatic sequences, morphic sequences, substitutions, abelian equivalence, ...
Learning outcomes of the learning unit
The student will master fundamental notions seen during the lectures as well as the corresponding proofs. He will be able to present them clearly and succinctly. Also, he will be able to apply those notions in order to solve related problems.
Prerequisite knowledge and skills
Basic mathematical knowledge from a bachelor degree in mathematics.
Planned learning activities and teaching methods
Theoretical lectures using "blackboard and chalk" or beamer, interacting with students. During exercises sessions, students could face exercises that must be solved on a computer.
Mode of delivery (face to face, distance learning, hybrid learning)
Blended learning
Additional information:
Lectures are mainly dedicated to theoretical aspects. Pratical sessions are devoted to solve exercises and to enlighten the concepts presented during the lecture. It could be considered to implement some algorithms or constructions in a computational software like Mathematica or Sage. Detailed schedule will be given at the beginning of the academic year.
The course will be organized in face-to-face, except maybe for some parts where podcasts will be available.
Part of the exercises will consists in homeworks.
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. 2, Applications to recognizability and decidability, ISTE-Wiley (2014).
- 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).
- 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).
- J. Shallit, A second course in formal languages and automata theory, Cambridge University Press (2008).
An oral examination devoted to the theory (mainly statements and proofs of theorems and discussion) but also direct applications of the theory is organized. Homeworks could possibly be taken into account for the final grade.
Work placement(s)
Organisational remarks and main changes to the course
This course is given in English. It is organized on academic years starting on an odd year (for instance 2017-2018).
Contacts
J. Leroy, Institut de Mathématique (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège Tél. : (04) 366.94.70 - E-mail : j.leroy@uliege.be ;