Aims and Scope -- Our Sponsors --
Poster Download
#### School on Combinatorics, Automata and Number Theory - Liège June 2009

From **1st to 5th June 2009**, the second edition of the summer
school CANT will be organized in Liège. The first edition
was organized in May 2006 and gathered around 100 participants.

This time, we propose in Liège two joint events connected to automata in the wide sense. During the week following this school will be organized the AutoMathA conference (8-12 June 2009). The AutoMathA programme is a five-year multidisciplinary programme (2005-2010), at the crossroads of mathematics, theoretical computer science and applications, gathers 14 European countries. The goal of AutoMathA is to propose a set of co-ordinated actions for advancing the theory of automata and for increasing its application to challenging scientific problems. See http://www.esf.org/automatha for more details. See our sponsors below.

**Some of the slides are available**

The main**topics of this school** are (4 hours and a half for each subject)
**Note** : A book (to appear in the Encyclopedia for Mathematics
and its Applications, Cambridge University Press) is in preparation
and will contain 10 chapters amongst them 6 corresponding to the
lectures given during the school.

This time, we propose in Liège two joint events connected to automata in the wide sense. During the week following this school will be organized the AutoMathA conference (8-12 June 2009). The AutoMathA programme is a five-year multidisciplinary programme (2005-2010), at the crossroads of mathematics, theoretical computer science and applications, gathers 14 European countries. The goal of AutoMathA is to propose a set of co-ordinated actions for advancing the theory of automata and for increasing its application to challenging scientific problems. See http://www.esf.org/automatha for more details. See our sponsors below.

- Vincent Blondel's lecture
- Raphael Junger's lecture 1
- Raphael Junger's lecture 2
- Anne Siegel's lecture 1
- Anne Siegel's lecture 2
- Anne Siegel's lecture 3

The main

- Number representation and finite automata
- Factor complexity
- Tilings, substitutions and Rauzy fractals
- Block frequencies in infinite words and invariant measures
- Transcendence and Diophantine approximation
- Maximal products of matrices and the finiteness property

It is a difficult task to briefly present the main subjects of the school, however they can be succinctly explained as follows. Combinatorics, and more specifically combinatorics on words, deals with problems that can be stated in a noncommutative monoid such as subword complexity of finite or infinite words, construction and properties of infinite words, block frequencies, unavoidable regularities or patterns,.... A fruitful use of word combinatorics is its contribution to the study of dynamical systems, such as illustrated by the interplay between notions like minimality and uniform recurrence, or unique ergodicity and uniform frequencies. For instance, the coding of orbits and trajectories by words, constitutes the basis of symbolic dynamical systems: A historical example dating back to 1921, is the study by H. M. Morse of recurrent geodesics on a surface with negative curvature. As an other example, these similar ideas are found in connection with the Word Problem in group theory. Moreover the use of combinatorics is sought in the analysis of algorithms, initiated by D. E. Knuth, and which greatly relies on number theory, asymptotic methods and computer algebra. When considering some numeration system, any integer can be represented as a finite word over an alphabet of digits. This simple observation leads to the study of the relationship between the arithmetical properties of the integers and the syntactical properties of the corresponding representations. One of the deepest results in this direction is given by the celebrated Cobham's theorem. Surprisingly, a recent extention of this latter result to the complex numbers leads to the famous Four Exponentials Conjecture. This is just one example of the fruitful relationship between formal language theory (including the theory of automata) and number theory. Other examples are given by the study of digital functions, automatic sequences and the transcendence of formal power series, the Rauzy fractal and discrepancy problems and by the representation of real numbers in various numeration systems. This latter problem is in particular related to Diophantine analysis or approximations of real numbers to algebraic numbers, which has recently enjoyed striking developments through a fruitful interplay between Diophantine approximation and combinatorics on words. On the other hand, we have to keep in mind that both combinatorics on words and theory of formal languages have important applications and interactions in computer science and physics. To cite just a few: dynamical systems and control theory, study and models of quasicrystals, aperiodic order and quasiperiodic tilings, bioinformatics and DNA analysis, theory of parsing, algorithmic verification of large systems, coding theory, discrete geometry and more precisely discretization for computer graphics on a raster display,....Let us quote as a particularly striking example the problem of maximizing products of matrices taken from a finite set. Indeed the joint spectral radius is of great interest in a number of diverse applications, including word combinatorics.