L’équipe travaille dans le domaine de l’informatique théorique et est composée de spécialistes de domaines différents mais connexes : calculabilité, complexité, logique. Ses membres se retrouvent dans les objets qu’ils étudient, et typiquement, ces objets sont les pavages, les automates cellulaires, les machines de Turing. Ils se retrouvent aussi dans les paradigmes qu’ils adoptent : la spécialité de l’équipe est de travailler sur ces objets d’un point de vue « modèle de calcul », mais nous nous intéressons aussi largement à la « théorie des jeux algorithmiques ». Nous cherchons à comprendre aussi bien l’émergence de la notion de calcul que la puissance ou à la robustesse des modèles considérés. Nos travaux ont un impact hors de notre champ scientifique propre : en mathématiques dans le domaine des systèmes dynamiques discrets, en logique, et ils commencent à avoir un impact en physique statistique.
Permanents
Alexander Shen, Directeur de recherche, CNRS
Bruno Durand, Professeur des universités, UM
Patrice Séébold, Professeur des universités, UPVM
Matthieu Rosenfeld, Maître de conférences, UM
Victor Poupet, Maître de conférences, UM
Gwenaël Richomme, Professeur des universités, UPVM
Doctorants
Autres personnels
Geoffroy Caillat Grenier, CDD Ingénieur-Technicien, CNRS
Nos objets :
- pavages
- automates cellulaires
- mots (dimension 1 et 2)
Nos approches :
- calculabilité
- complexité
- combinatoire
- logique
- algorithmique
Internationales :
- Leonid Levin et Peter Gacs – Boston University, USA
- Theodore Slaman – Univ. of California, Berkeley, USA
- Jarkko Kari – University of Turku, Finlande
- Nikolai Vereshchagin – Moscow University, Russia
- Menachem Magidor – Hebrew U. Jérusalem, Israël
- Katsunobu Imai – Hiroshima University, Japan
Nationales :
- Emmanuel Jeandel – Loria, Nancy
- Nicolas Ollinger – LIFO, Orléans
- Enrico Formenti – I3S, Nice
- Laurent Bienvenu – LIAFA, Paris
- Gaëtan Richard – Greyc, Caen
Notre groupe de travail est composé d’exposés d’orateurs invités et d’orateurs locaux (environ pour moitié). Il est commun avec l’équipe ECO et est organisé par Bruno Grenet et Andrei Romashchenko.
Titre : Graphes expanseurs et applications à la cryptographie en théorie de l’information.
Doctorant : Geoffroy Caillat Grenier
Date de soutenance : 2024-12-10
Directeurs de thèse :
Alexander Shen,
Andrei Romashchenko
Titre : L’inférence d’inégalités d’information non classiques et leurs applications.
Doctorant : Emirhan Gürpinar
Date de soutenance : 2022-12-08
Directeurs de thèse :
Alexander Shen,
Andrei Romashchenko
Titre : Étude de la complexité algorithmique et du caractère sofic des shifts en dimension deux
Doctorant : Julien Destombes
Date de soutenance : 2021-12-17
Directeur de thèse :
Andrei Romashchenko
Titre : Couverture d’un mot bidimensionnel par un motif chevauchant
Doctorant : Guilhem Gamard
Date de soutenance : 2017-06-30
Directeur de thèse :
Gwenaël Richomme
Titre : Reconnaissance de Langage en temps réel sur automates cellulaires 2D
Doctorant : Anael Grandjean
Date de soutenance : 2016-12-06
Directeur de thèse :
Bruno Durand
Titre : Construction de liens entre algorithmique et logique par du calcul à temps infini.
Doctorant : Sabrina Ouazzani
Date de soutenance : 2016-12-02
Directeur de thèse :
Bruno Durand