### Duration

30h Th, 10h Pr, 20h Mon. WS

### Number of credits

Master in mathematics (120 ECTS) | 10 crédits | |||

Master in mathematics (60 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