Systèmes Dynamiques et Calcul: une approche logique – DySCo

DySCo prendra appui sur la théorie des Graphes d'Interaction de Seiller pour revisiter les fondements de l'informatique au travers de la théorie des systèmes dynamiques. En effet, le travail de Seiller montre que les graphages – une généralisation des systèmes dynamiques – fournissent un modèle des programmes informatiques expressif et puissant. DySCo dévellopera des définitions formelles satisfaisantes pour les notions calculs, programmes, et algorithmes qui seront à la fois suffisamment générales pour capturer de nombreux modèles de calcul et suffisamment précis pour fournir des modèles algorithmiquement complets. Ces fondements théoriques permettront d'étendre le champ d'application de la correspondance de Curry-Howard entre logique et informatique, ainsi que le transfert d'outils et méthodes de la théorie des systèmes dynamiques en informatique théorique, ouvrant notamment de nouvelles pistes pour prouver des résultats de bornes inférieures en complexité algorithmique.