Duration
30h Th, 10h Pr, 20h Mon. WS
Number of credits
| Master in mathematics (120 ECTS) | 10 crédits |
Lecturer
Coordinator
Language(s) of instruction
French language
Organisation and examination
All year long
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 (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.
Learning outcomes of the learning unit
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 systems 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 number systems (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 or ergodic theory, ...
At the end of this course, the student will be able to work autonomously, acting 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.
Prerequisite knowledge and skills
It is assumed that the student has a good background in discrete mathematics (e.g. graph theory, discrete mathematics, computability, formal language theory, combinatorics on words, ...). In order to register for this course, the interested student must have a coherent program of study and demonstrate his/her motivation to develop a personal research activity (for instance, starting a Ph.D. or be introduced to state of the art results). The course organizers reserve the right to accept or reject a student registration. Prior to the start of the academic year, the student is invited to have an open discussion with the organizers.
Planned learning activities and teaching methods
Reading, summarizing and presenting research papers and text books, participating in seminars and reading groups, tailored courses, problem solving.
Mode of delivery (face to face, distance learning, hybrid learning)
Face-to-face course
Additional information:
This course, preparing to research, needs an active participation of the student. In order to learn the concepts independently, personal work and oral presentations given by the students will be sought. It is expected that students will mostly work alone. Appointements will also be scheduled.
Recommended or required readings
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).
- V. Berthé, M. Rigo (Eds.), Combinatorics, Words, Symbolic Dynacmics, Cambridge University Press (2015).
- 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).
Exam(s) in session
Any session
- In-person
oral exam
Continuous assessment
Additional information:
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)
Organisational remarks and main changes to the course
Contacts
E. Charlier
Institute of Mathematics (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.93.84 - E-mail : echarlier@ulg.ac.be
J. Leroy
Institute of Mathematics (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.70 - E-mail : j.leroy@ulg.ac.be
M. Rigo
Institute of Mathematics (B37) - Allée de la découverte 12 - Sart Tilman, 4000 Liège
Tél. : (04) 366.94.87 - E-mail : M.Rigo@ulg.ac.be