On monday, at 2pm - UPEC CMC - Room P2-131

January 24, 2022

TBA

Nathan Grosshans (Universität Kassel)

November 15, 2021

tba

Mahsa Shirmohammadi (IRIF)

October 18, 2021

Simulating Digital Computations with Analog Machines

Olivier Bournez (Lix)

We will compare the power of analog machines (such as the General Purpose Analog Computer), based for example on analog electronics, to the power of digital machines (such as Turing machines). This will involve a discussion on how one can compute with ordinary differential equations.

October 11, 2021

Expressions régulières pour transducteurs apériodiques

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.