Duration
30h Th, 20h Pr
Number of credits
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.
Course materials and 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).
Exam(s) in session
Any session
- In-person
written exam ( open-ended questions ) AND oral exam
Written work / report
Further information:
The final assessment may take one of the following two forms:
- a traditional examination, consisting of an oral component covering the theory and a written component focusing on exercises and the direct application of the theoretical concepts;
- a combined assessment, consisting of an oral examination covering the theory, a short written exercise, and a presentation of projects.
In either case, the chosen assessment format will aim to evaluate students' mastery of the theoretical knowledge, their ability to apply this knowledge in practice, and the quality of the work completed throughout the academic year.
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
Manon Stipulanti
Institut de Mathématique (B37)
Allée de la découverte 12
Sart Tilman, 4000 Liège
E-mail : m.stipulanti@uliege.be