Soutenance de thèse de GOUBAULT--LARRECQ Aliénor
Titre de thèse
Méta-théorèmes de bornes inférieures de complexité pour les systèmes dynamiques finis
Metatheorems of complexity lower bounds for finite dynamical systems
Résumé de la thèse
Cette thèse porte sur les bornes de complexité générales des questions exprimables en logiques de graphes dans des systèmes dynamiques finis, en particulier sur la dynamique de réseaux d'automates, similaire à une représentation succincte de graphe.
En s'appuyant sur les travaux de Gamard, Guillon, Perrot et Theyssier [STACS 2021; Preprint 2023], cette thèse généralise deux résultats de NP‑ et coNP‑difficulté pour les formules du premier‑ordre, en considérant des réseaux d'automates dits déterministes, et du second‑ordre monadique sur toutes les représentations succinctes de graphes. Ces deux métathéorèmes sont de la forme "Étant donné une formule psi décrivant une propriété, le problème de décider si la dynamique d'un réseau d'automates vérifie psi est soit trivial soit NP- ou coNP-difficile" et ainsi donnent des bornes inférieures de complexité.
Les contributions principales de cette thèse se sont concentrées sur l'extension de chaque aspect de ces métathéorèmes : les propriétés et les formules considérées, mais aussi les réseaux d'automates considérés et leurs caractéristiques. En particulier, concernant les propriétés exprimables, on enrichit les formules par l'ajout de relations décrivant des aspects non considérés auparavant des réseaux d'automates et on étudie des restrictions promettant certaines caractéristiques de l'entrée donnée pour un problème de décision (par exemple, le déterminisme). Concernant les réseaux d'automates, on étend les résultats utilisant auparavant le paramètre tree-width au paramètre plus général clique-width et on prouve que l'obtention de bornes inférieures est aussi possible pour des réseaux d'automates à alphabet fixé, notamment lorsque tous les automates partagent le même alphabet.
Chaque résultat fournit une borne inférieure de complexité, et cette thèse étudie également l'utilisation d'autres paramètres structuraux, et de la limite atteinte par nos résultats de complexité utilisant les clique-width.
Thesis resume
This thesis focuses on general complexity bounds for questions expressible in graph logics within finite dynamical systems, in particular on the dynamics of automata networks, similar to succinct graph representations.
Building on the work of Gamard, Guillon, Perrot and Theyssier [STACS 2021; Preprint 2023], this thesis generalizes two NP- and coNP-hardness results for first-order formulas, by considering so-called deterministic automata networks, and for monadic second-order logic over all succinct representations of graphs. These two metatheorems are of the form "Given a formula psi describing a property, the problem of deciding whether the dynamics of an automata network satisfies psi is either trivial or NP- or coNP-hard", and thus provide complexity lower bounds.
The main contributions of this thesis have focused on extending every aspect of these metatheorems: the properties and formulas considered, but also the automata networks considered and their characteristics. In particular, regarding expressible properties, we enrich the formulas by adding relations describing aspects of automata networks not previously considered, and we study restrictions promising certain characteristics of the input given to a decision problem (for example, determinism). Regarding automata networks, previous results were using the parameter tree-width and we extend them to tree-width to the more general parameter clique-width, and we prove that obtaining lower bounds is also possible for automata networks with a fixed alphabet, notably when all automata share the same alphabet.
Each result provides a complexity lower bound, and this thesis also studies the use of other structural parameters, and the limit reached by our complexity results using clique-width.