Satellite AlgoComb de la journée Maths-STIC du 20 mai 2016

Les automates traditionnels (automates de Kleene) sont un modèle naturel et simple pour représenter des programmes séquentiels: les mots reconnus peuvent être vus comme des traces d’exécution de programmes séquentiels. Dans cet exposé nous nous intéressons aux automates branchants, définis et étudiés par Lodaya & Weil il y a une quinzaine d’années. Les automates branchants sont une extension des automates de Kleene avec deux nouvelles catégories de transitions permettant de mettre en parallèle des chemins de l’automate. Les étiquettes des chemins ne sont plus alors des mots (ordres totaux), mais des pomsets (ordres partiels), qui peuvent aussi être vus comme des traces d’exécution de programmes concurrents. Le complémentaire du langage d’un automate de Kleene est encore le langage d’un automate de Kleene, et ce dernier se calcule effectivement (et facilement) à partir du premier. Ce calcul peut être réalisé par plusieurs constructions bien connues. L’une d’entre elles repose sur une construction algébrique, réalisable car l’algèbre associée à un automate est finie. Nous verrons que cette construction se généralise aux automates branchants, mais elle est plus difficile, car cette fois-ci les algèbres associées aux automates peuvent être infinies.

La conjecture de la dichotomie énoncée il y a bientôt 25 ans par Feder et Vardi stipule que tout problème de contraintes est soit dans P, soit NP-complet. Ces problèmes peuvent être formulés comme des problèmes de model checking paramétrés par la structure où la logique considérée est un certain fragment de la logique du premier ordre : la formule représente la partie syntaxique d’une instance du problème de contrainte (c’est-à-dire les variables et les contraintes imposés entre ces variables) et la structure décrit la nature même de ces contraintes, c’est-à-dire les combinaisons de valeurs autorisées. Dans le cas booléen, qui correspond à une variante du problème SAT, la conjecture est supportée par le théorème de Schaefer, dont la preuve repose sur une machinerie algébrique proposée par Post. Cette machinerie peut être adaptée pour résoudre des problèmes  de model checking différents. Dans cet exposé, je me propose de présenter une introduction vulgarisée à cette problématique puis de commenter quelques résultats de classification.

Dans cet exposé, nous présentons une transformée bijective de type Burrows-Wheeler pour les mots binaires. La méthode originale par Burrows et Wheeler est basée sur l’ordre lexicographique pour les alphabets généraux. La transformation d’un mot est donc définie comme étant la dernière colonne de la matrice constituée par les conjugués du mot triés dans l’ordre croissant. Notre nouvelle approche applique l’ordre des blocs binaires, appelé B-ordre, ce qui, en fait, donne non pas une, mais deux transformées : une basée sur des mots de Lyndon, l’autre sur une répétition de mots de Lyndon. Ces transformées sont construites pour les B-mots qui sont des analogues aux mots de Lyndon (plus petits conjugués dans l’ordre considéré). Un calcul clé dans ces transformations est l’application d’une technique de tri des suffixes en temps linéaire. De plus, nous montrons que le calcul des inverses de ces transformées peut se faire en temps linéaire en utilisant des arguments combinatoires simples.

Les mots sturmiens sont intensément étudiés,  car ce sont  (informellement) les mots les plus simples non ultimement périodiques.  Nous  adoptons ici un point de vue  peu  classique,  et nous nous intéressons à l’étude d’un mot sturmien aléatoire.  Il est bien connu que tout mot sturmien est défini par son angle $\alpha$, qui est un irrationnel de l’intervalle $]0, 1[$.    Il est donc naturel   de travailler dans un modèle aléatoire où  l’angle $\alpha$  est uniforme dans l’intervalle $]0, 1[$. Nous étudions ainsi  la fonction de récurrence $(\alpha, n)  \mapsto R_\alpha (n)$   qui  décrit le temps d’attente nécessaire pour obtenir tous les facteurs de longueur donnée $n$ du mot sturmien $S_\alpha$, où  l’angle $\alpha$ est uniforme dans $]0, 1[$  et la longueur $n$  uniforme dans $[1..N]$, quand la borne $N$ tend vers $\infty$. Je présenterai les résultats obrenus, et  je chercherai aussi à relier cette étude aléatoire avec des préoccupations  sturmiennes rouennaises (Lecroq, Lefevre et Prieur-Gaston). Ces derniers  étudient  l’indice d’un mot sturmien, qui  décrit la périodicité locale du mot, et surtout la version abélienne  de ce paramètre.