Tito's presence on the Web

Ma soutenance de thèse

Quand ?

Le vendredi 3 décembre 2021 à 14h (UTC+1, c’est aussi bien le fuseau horaire de Paris que de Varsovie en hiver).

Où ?

En ligne : sur le logiciel libre BigBlueButton ici ; connectez-vous en écoute seule

En présentiel : salle B107 au Laboratoire d’informatique de Paris Nord, à Villetaneuse

Quoi ?

Le sujet : Automates implicites en logique linéaire et théorie catégorique des transducteurs

Le manuscrit : par ici

Jury

Résumé

Cette thèse cherche à établir de nouveaux liens entre deux domaines distincts au sein de l’informatique théorique : d’une part la théorie des automates, dont les objets d’étude sont des modèles de calcul à mémoire limitée, et d’autre part celle des langages de programmation, en particulier du λ-calcul qui sert de base au paradigme fonctionnel.

Il est connu que les fonctions des mots vers les booléens définissables par des programmes écrits en λ-calcul simplement typé, en utilisant les codages de Church, correspondent exactement aux langages rationnels. Partant de là, nous employons des λ-calculs à types linéaires pour caractériser plusieurs autres classes de langages et de fonctions sur les mots (voire sur les arbres) provenant de la théorie des automates. Afin de démontrer ces résultats, nous tissons des liens entre les sémantiques dénotationnelles – qui nous servent à évaluer les λ-termes – et la théorie catégorique des automates; en particulier, nous montrons que les catégories monoïdales closes, qui apparaissent en sémantique de la logique linéaire, fournissent également une base pour généraliser quelques constructions sur les automates qui font moralement intervenir des espaces de fonctions. Nos recherches sur les λ-calculs linéaires nous mènent également à introduire et étudier un nouveau modèle de transducteurs qui calcule des fonctions sur les mots à croissance polynomiale.