Home » Évènement » Soutenance de thèse de Bastien Sérée
Loading Events
  • This event has passed.

Soutenance de thèse de Bastien Sérée

15 décembre 2022 @ 10 h 00 min

Bastien Sérée, doctorant au sein de l’équipe STR, soutiendra sa thèse intitulée :

« Problèmes d’optimisation dans les graphes paramétrés » / « Optimisation problems in parametrized graphs »

Le 15 décembre 2022 à 10h, dans l’amphithéâtre B 008, sur le site de l’École Centrale

 

Jury :
– Directeur de thèse : Didier Lime
– Encadrant : Loïg Jezequel
– Examinateur·rice·s : Nathalie Sznajder, Nicolas Markey, Stéphane Le Roux, Pierre-Alain Reynier et Etienne André
– Rapporteurs : Pierre-Alain Reynier et Etienne André

 

Résumé :

Nous considérons des graphes orientés pondérés dont l’énergie est paramétrée. Nous proposons dans un premier temps un algorithme qui, étant donné un graphe et un de ses sommets, renvoie des arbres, chaque arbre représentant les plus courts chemins depuis la source vers tous les autres sommets du graphe pour une zone particulière de l’espace des paramètres. De plus l’union de ces zones couvre l’espace des paramètres. Nous considérons ensuite l’accessibilité dans les graphes à énergie multi-dimensionnelle, avec un type de contraintes plus absolues qui imposent que l’énergie reste entre des bornes. Nous montrons la décidabilité et la complexité du problème quel que soit le nombre de paramètres et de dimensions lorsque les paramètres prennent des valeurs entières. Nous montrons également l’indécidabilité de ce problème avec au moins un paramètre lorsque la dimension est supérieure ou égale à deux. Nous étudions enfin des jeux de parité à un et deux joueurs sur les graphes paramétrés dont l’objectif est la conjonction d’une condition qualitative sur la parité et d’une condition quantitative : l’énergie doit rester positive. Nous montrons la décidabilité et prouvons des bornes de la complexité du problème de la recherche d’une stratégie gagnante dans les cas à un et à deux joueurs.

 

Mots-clés : automate, graphes paramétrés, plus court chemin, jeux sur les graphes, objectifs de parité, contraintes sur l’énergie, model-checking.


Abstract:
We are considering weighted oriented graphs with parametrized energy. Firstly we propose an algorithm that, given a graph and one of its vertices, returns trees, every tree representing shortest-paths from the source to every other vertex for a particular zone of the parameter space. Moreover, union of these zones is a covering of the parameter space. Then we consider reachability in graphs with multi-dimensional energy, with stricter constraints that enforce the energy to stay between bounds. We prove decidabilty and complexity of this problem regardless of the dimension and the number of parameters when parameters take integer values. We also prove the undecidability of this problem when there is at least one parameter and the dimension is at least two. Finally we study parity games on parametrized graphs with one and two players whose objective is the conjunction of a qualiative condition on the parity and quantitative one : energy must stay positive. We show the decidability and prove bounds on the complexity of the problem of searching a winning strategy in both cases with one and two players.

 

Keywords: automata, parametrized graphs, shortest paths, games on graphs, parity objectives, energy constraints, model-checking

 

Détails

Date :
15 décembre 2022
Heure :
10 h 00 min
Organisateur
LS2N

Catégorie d’Évènement:
Évènement Tags:

Lieu

Centrale Nantes
Copyright : LS2N 2017 - Mentions Légales - 
 -