News

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

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

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

Une journée de l’axe Algorithmique et Combinatoire est organisée le 19 mai de 14H à 18H, veille de la Journée Maths-Stic.

Salle de séminaire du Département d’Informatique
UFR de Sciences & Technologies
Site du Madrillet
Université de Rouen.
Programme:
  • 14h-14h45 : Nicolas Bedon: Le complémentaire du langage d’un automate branchant est encore le langage d’un automate branchant.
    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.
  • 14h45-15h30: Florent Madelaine: Complexité du model checking paramétré par la structure.

    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.

  • 15h30-15h45: Pause
  • 15h45-16h30: Thierry Lecroq: La transformée dans l’ordre des blocs binaires.
    (Travail commun avec Jackie Daykin, Richard Groult, Yannick Guesnet, Arnaud Lefebvre, Martine Léonard et Elise Prieur-Gaston)
     

    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.
  • 16h30-17h15: Brigitte Vallée: Fonction de récurrence d’un mot sturmien aléatoire
    (Travail commun avec Pablo Rotondo)

    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.

  • 17h15-18h: Discussions sur l’axe.

 

Leave a Comment

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>