Reference : Jouer avec les mots, pourquoi et comment ?
Scientific conferences in universities or research centers : Scientific conference in universities or research centers
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/184489
Jouer avec les mots, pourquoi et comment ?
English
Rigo, Michel mailto [Université de Liège > Département de mathématique > Mathématiques discrètes >]
4-Aug-2015
National
Brussels Summer School of Mathematics
from 3-8-2015 to 7-8-2015
Brussels
[en] combinatorics on words ; number theory ; discrete geometry
[en] A l'instar de Raymond Queneau et ses cent mille milliards de poèmes, cet exposé a pour but de compter et de construire des mots aux propriétés parfois surprenantes. Les premiers résultats en combinatoire des mots remontent au début du siècle précédent, avec les travaux du mathématicien norvégien Axel Thue. Cette branche des mathématiques étudie la structure et les arrangements apparaissant au sein de suites finies, ou infinies, de symboles appartenant à un ensemble fini.

Donnons un exemple rudimentaire. Un carré est la juxtaposition de deux répétitions d'un mot, ainsi "coco" ou "bonbon" sont des carrés. On dira alors qu'un mot comme "taratata" contient un carré. Il est aisé de vérifier que, si on dispose uniquement de deux symboles "a" et "b", alors tout mot de longueur au moins 4 contient un des carrés "aa", "bb", "abab" ou encore "baba". On dira donc que, sur deux symboles, les carrés sont inévitables.

Cette observation pose des questions intéressantes et simples à formuler : Avec trois symboles, peut-on construire un mot arbitrairement long ne contenant pas de carré ? Si on se limite à deux symboles, peut-on construire un mot arbitrairement long sans cube, i.e., évitant la juxtaposition de trois répétitions d'un même mot ? En fonction de la taille de l'alphabet, quels motifs doivent nécessairement apparaître et quels sont ceux qui sont évitables ? Que se passe-t-il si on autorise certaines permutations ? etc.

Dans cet exposé, on passera en revue quelques constructions simples de mots finis ou infinis : mot de Thue-Morse, mot de Fibonacci, mots Sturmiens. Nous montrerons aussi que les applications sont nombreuses : arithmétique, transcendance en théorie des nombres, informatique mathématique et théorie des automates, pavages du plan, dynamique symbolique et codage de rotations, infographie, géométrie discrète et représentation de segment de droites à l'écran, bio-informatique, ...
Researchers ; Students
http://hdl.handle.net/2268/184489

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
Rigo.pdfAuthor preprint976.12 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.