Cette demi-journée aura lieu le 5 mai à Luminy, en salle 04.05 du TPR2, à 10h.
Orateur : Édouard Bonnet
Titre : Graph decompositions and their algorithms
Résumé : Through simple examples, we take a representative glimpse at forty years of using width parameters for algorithmic purposes. The talk will be biased towards revisiting this history through the lens of contraction sequences, which are at the basis of the recently introduced twin-width.
Orateur : Karoliina Lehtinen
Titre : Un peu de non-déterminisme peut aller loin: un aperçu des automates déterministes en histoire
Résumé : Le non-déterminisme permet surement à votre modèle d’automate préféré plus expressif, ou du moins plus succinct que le déterminisme. Cela se fait généralement au au prix d’une complexité algorithmique plus importante. Les classes d’automates intermédiaires, entre déterministes et non-déterministes, présentent des compromis intéressants en ce qui concerne l’expressivité, la succincté et les propriétés algorithmiques.
Les automates déterministes en histoire sont des automates non-déterministes dans lesquels les choix non-déterministes peuvent être faits sans connaître le futur du mot d’entré. Ils combinent une partie de la succincté et de l’expressivité des automates non déterministes avec certaines des propriétés algorithmiques utiles des automates déterministes. En particulier, les jeux avec des conditions gagnantes données par des automates déterministes en histoire ont tendance à être plus simples à résoudre que les jeux dont les conditions de gain sont non-déterministes.
Dans cet exposé, je donnerai une vue d’ensemble des automates déterministes en histoire, de leur relation avec divers problèmes de synthèse et des développements récents dans le domaine pour différentes classes d’automates.
Orateur : Nathan Lhote
Titre : Minimisation des transductions rationnelles
Résumé : La notion d’automate minimal (ou de monoïde syntaxique) fournit pour les langages réguliers un objet canonique qui capture beaucoup de propriétés intrinsèques d’un langage. Par exemple le théorème de Schützenberger nous dit qu’un langage est définissable en logique du premier ordre FO[<] si et seulement si son automate minimal est sans compteur. Depuis de nombreux résultats similaires ont été obtenus, faisant des liens entre expressivité dans une certaine logique et propriété de l’automate minimal.
Un transducteur est un automate équipé de sorties. Contrairement au cas des langages, les transducteurs ne sont pas toujours déterminisables. Pour les transducteurs, il n’existe certes pas d’automate minimal mais on montre qu’il existe un nombre fini de bimachines (modèle de calcul introduit par Schützenberger et étudié par Eilenberg) qui capturent (dans le même sens que l’automate minimal pour les langages) les propriétés d’une transduction.