October 11, 2021
Luc Dartois (LACL)La classes des fonctions régulières est une classe robuste définie de façon équivalente par les transducteurs bidirectionnels, les transductions MSO ou encore les Streaming String Transducers. Récemment, il a été proposé des combinateurs réguliers afin de définir des expressions régulières pouvant décrire cette classe.
Dans cet exposé, je présenterai la classe des transducteurs bidirectionnels ainsi que ces combinateurs réguliers, puis une extension de ce résultat à la sous-classe des fonctions apériodiques, étendant le célèbre résultat d’équivalence entre expressions sans-étoiles et automates apériodiques de Schützenberger.
Les résultats présentés ici proviennent de travaux récents en collaboration avec Paul Gastin (LSV, Université Paris-Saclay) et Shankara Narayanan Krishna (IIT Bombay) et sont disponible à cette adresse.