IRP Le Trójkąt : Logique, jeux et automates créent des liens entre France et Pologne
Qu’est-ce que Varsovie, Paris, et Bordeaux ont en commun ? Ce sont trois berceaux pour la communauté de recherche travaillant autour de la théorie des automates, de la logique, et de la théorie des jeux. Les très nombreux échanges entre ces pôles et au-delà ont permis des avancées majeures dans ces domaines, récompensées au niveau international. L’objectif de l’International Research Project (IRP) Le Trójkąt est de structurer et de développer ces relations, pour s’attaquer aux problèmes que le XXIe siècle inspire à l’informatique fondamentale.
Les collaborations scientifiques en sciences informatiques entre la France et la Pologne sont bien plus anciennes que celles dont il est question ici. Dès les années 1990, des liens étroits ont été tissés dans les domaines de la logique, de la théorie des automates et des langages de programmation, par exemple : Damian Niwinski, professeur à l'Université de Varsovie, en Pologne, Igor Walukiewicz, directeur de recherche CNRS au Laboratoire bordelais de recherche en informatique (LaBRI - CNRS/Bordeaux INP/Université de Bordeaux) et André Arnold, professeur retraité de l'Université de Bordeaux.
Ces échanges ont pris de l’ampleur au cours des années, et aujourd’hui une partie importante de la communauté de recherche autour de la logique, des jeux, et des automates, gravite autour du groupe Automates de l’Université de Varsovie, de l’équipe Automates de l’Institut de recherche en informatique fondamentale (IRIF - CNRS/Université de Paris) à Paris, et du département Méthodes et Modèles Formels du LaBRI. De nombreuses initiatives ont donné de l’élan à ces interactions, notamment lors de la conférence annuelle Highlights of Logic, Games, and Automata ou des séminaires Autobóz.
Parmi les succès récents obtenus à travers des collaborations entre chercheurs de ces trois pôles, citons la résolution d’un problème ouvert depuis plusieurs décennies : la complexité de l’accessibilité dans les réseaux de Petri1 . Ces résultats sont dus en particulier à Wojciech Czerwinski, professeur à l'Université de Varsovie, Sławomir Lasota, professeur à l'Université de Varsovie, Jérôme Leroux, directeur de recherche CNRS au LaBRI, et Filip Mazowiecki, professeur à l'Université de Varsovie, anciennement membre du LaBRI et qui a depuis rejoint Varsovie. D’importants progrès ont également été réalisés par des chercheurs de ces trois pôles sur une autre problématique centrale en informatique fondamentale, la complexité de la résolution des jeux de parité.
Un prix du meilleur article de la conférence ACM Symposium on Theory of Computing a donné un nouvel élan à la communauté en 2017, en construisant un algorithme en temps quasi polynomial, balayant les approches précédentes. Paweł Parys, professeur à l'Université de Varsovie et Nathanaël Fijalkow, chargé de recherche CNRS au LaBRI ont prouvé une borne inférieure sur ces nouvelles approches, suggérant qu’il reste encore beaucoup à comprendre sur ce problème vieux de plus de trente ans et central pour la théorie et la pratique de la synthèse réactive.
L’objectif de l’IRP Le Trójkąt est d’encourager les collaborations entre la France et la Pologne autour des thématiques dites “Track B” de l’informatique fondamentale : logique, jeux, automates, graphes. En étendant ces actions au-delà du triangle Paris - Bordeaux - Varsovie, l’IRP Le Trójkąt implique le CRIStAL (Lille), le DI ENS (Paris), l’IRISA (Rennes), le LIP (Lyon), le LIS (Marseille), le LMF (Saclay), et Wrocław, en Pologne. À travers l’organisation d’évènements scientifiques (écoles de recherche, séminaires) et le soutien financier et logistique de stages et visites de recherche, l’IRP Le Trójkąt encourage ces échanges, afin d’attaquer ensemble les problèmes ouverts les plus importants en informatique fondamentale.
- 1Czerwinski, Wojciech, Slawomir Lasota, Ranko Lazic, Jérôme Leroux and Filip Mazowiecki. “The Reachability Problem for Petri Nets Is Not Elementary.” Journal of the ACM (JACM) 68 (2018): 1 - 28. https://doi.org/10.48550/arXiv.1809.07115
Pour en savoir plus
Consultez le site internet de l'IRP Le Trójkąt