ECOLE DE RECHERCHE
CANT 2016 (Combinatoire, Automates et Théorie des Nombres)
28 novembre au 2 décembre 2016

Cette conférence internationale CANT s’intéresse aux développements récents en combinatoire des mots, en théorie des automates et langages formels ainsi qu’en théorie des nombres. La motivation première de ce projet est d’exploiter les interactions fructueuses et non triviales existant entre ces différents domaines de recherche. Une préoccupation majeure de ce projet est la formation des doctorants et des jeunes chercheurs. Les thèmes de CANT se situent à  l’interface entre mathématiques et informatique théorique et s’appuient sur un vaste panel d’outils : combinatoire, algèbre, arithmétique, dynamique (algébrique, symbolique, topologique), théorie ergodique, théorie des langages et des automates, calculabilité, complexités (algorithmique, de communication, de Kolmogorov), etc. L’informatique apporte ici des problématiques comme les problèmes de décision et de reconnaissabilité, alors que les mathématiques apportent des outils comme les systèmes dynamiques. Les mots et les automates finis jouent un rôle central dans le contexte de CANT, principalement en raison de la puissance de représentation des mots : ils offrent une manière naturelle de coder les éléments d’un ensemble infini en n’utilisant qu’un nombre fini de symboles. Les automates finis sont également connus pour leur puissance descriptive. C’est une idée naturelle si l’on pense aux automates finis comme permettant la représentation de sous-groupes finiment engendrés du groupe libre.
Comité scientifique

Shigeki Akiyama (University of Tsukuba)
Jean-Paul Allouche (Université Pierre et Marie Curie)
Valérie Berthé (Université Paris Diderot)
Srecko Brlek (Université du Québec, Montréal)
Karma Dajani (University of Utrecht)
Anna Frid (Aix-Marseille Université)
Jean Mairesse (Université Pierre et Marie Curie)
Michel Rigo (Université de Liège)
Jeffrey Shallit (University of Waterloo)
Boris Solomyak (University of Washington)

Comité d’organisation

Valérie Berthé (Université Paris Diderot)
Michel Rigo (Université de Liège)

Lectures

About the Domino problem on finitely generated groups

Amenable groups

Applications of algebra to automatic sequences and pattern avoidance.

Logic, decidability and numeration systems

Automorphism groups of low complexity subshift

  • Luca Zamboni (Université Claude Bernard Lyon 1)

Monochromatic factorisations of words and Ramsey theory

Exposés

Automatic sequences, generalised polynomials and nilmanifolds

Efficient repetition-free strings generator

  • Henk Don (Radboud University Nijmegen)

The Cerny conjecture and 1-contracting automata

On the Gap Between Separating Words and Separating Their Reversals

Densities of sets defined by sum-of-digits function

Entropy of topologically mixing subshifts

On the number of synchronizing colorings of digraphs

On the numbers of ergodic lifts over ergodic measures for finite-to-one factor maps between shifts of nite type

Quest for Short Identities in Transformation Semigroups and Symmetric Groups

Invariant measures of B-free shifts

On arithmetic index in the Thue-Morse word

Palindromic Length in Linear Time

Synchronization of Weakly Acyclic Automata

Synchronizing Coloring of a Graph