Soutenance de thèse de ROLLAND Marius

Résumé de la thèse

Un emph{système dynamique} fini, déterministe et à temps discret consiste en un couple $(A,f_A)$ où $A$ est un ensemble fini d'états et $f_A : A to A$ est une fonction totale de $A$ dans $A$, appelée emph{fonction de transition}.
Cette dernière définit l'évolution du système au cours du temps.
Cette dynamique est décrite de manière explicite par son graphe de transition, qui a les états du système pour sommets et, pour chaque état~$a in A$, un arc~$(a, f_A(a))$ le reliant à l'état suivant.
La forme générale de la dynamique d'un tel système consiste en un ou plusieurs emph{cycles limites} d'états périodiques (par exemple, $(a, f_A(a), f_A^2(a), ldots, f_A^n(a) = a)$ est un cycle limite de période~$n$), ainsi qu'en un régime transitoire d'états non périodiques en forme d'arbres, dont la racine appartient à l'un des états d'un cycle limite.

Ces systèmes, pris à isomorphisme près, sont appelé FDDS et sont particulièrement adaptés à la démarche scientifique.
En effet, ils sont non seulement largement utilisés pour vérifier qu'une spécification possède certaines propriétés attendues ou requises, mais aussi pour modéliser et analyser des phénomènes naturels, notamment en physique et en biologie.
Il est également possible de décrire des modèles de calcul déterministes usuels en informatique, tels que les automates cellulaires ou les machines de Turing à ruban borné, sous la forme de systèmes dynamiques finis.

Dans la littérature, il est connu que les FDDS, équipés d'opérations de somme (union disjointe) et de produit (produit direct), forment un semi-anneau commutatif.
Nous pouvons donc définir un semi-anneau de polynômes, ainsi que des équations polynomiales dont chaque coefficient et chaque variable est un FDDS.
Ce type d'équation est indécidable dans le cas général, mais appartient à la classe $NP$ lorsque l'un des côtés de l'équation est constant.
La résolution des équations de la forme $P(X_1,ldots,X_n) = B$ permet alors de déterminer si $B$ respecte certaines contraintes structurelles, mais aussi d'exhiber une dynamique sous-jacente.

Dans la présente thèse, nous nous concentrons essentiellement sur le cas où $P$ ne contient qu'une unique variable.
Nous fournissons un algorithme polynomial permettant de déterminer les comportements transitoires de toutes les solutions possibles de l'équation $P(X) = B$.
Nous donnons ensuite une méthode permettant de résoudre en temps polynomial les équations $P(X) = B$ lorsque $P$ satisfait une condition structurelle (injectivité, « pseudo-injectivité »).
Nous nous inspirons de cette approche pour mettre en évidence deux paramètres — le nombre de composantes connexes non isomorphes de $B$ et la plus petite longueur de cycle d'un coefficient non constant de $P$ — qui, lorsqu'ils sont fixés, permettent la résolution de $AX = B$ en temps polynomial.
Cela nous amène à étudier des sur- et sous-approximations de $B$.
En d'autres termes, nous introduisons des algorithmes polynomiaux permettant de résoudre les inéquations $P(X) le B$ et $P(X) ge B$.
Nous montrons également qu'il est possible d'énumérer l'ensemble des solutions de $P(X) le B$ avec un délai polynomial entre deux solutions.
Enfin, nous généralisons certains de nos résultats au cas où les systèmes ne sont plus décrits par des fonctions totales, mais par des fonctions partielles.