Complexity in Infinite Games on Graphs and Temporal Constraint Networks - Archive ouverte HAL Access content directly
Theses Year : 2017

Complexity in Infinite Games on Graphs and Temporal Constraint Networks

Complexité dans les Jeux Infinis sur les Graphes et les Réseaux de Contraintes Temporelles

(1)
1
Carlo Comin

Abstract

This dissertation deals with a number of algorithmic problems motivated by automated temporal planning and formal verification of reactive and finite state systems. We focused on game theoretical methods to obtain novel insights, improved complexity bounds, and faster algorithms for the following models: Hyper Temporal Networks, Conditional Simple/Hyper Temporal Networks, Update Games, Muller McNaughton Games, and Mean Payoff Games
Cette thèse porte sur un certain nombre de problèmes algorithmiques motivés par la planification temporelle automatisée et la vérification formelle des systèmes réactifs et finis. Nous nous sommes concentrés sur les méthodes théoriques des jeux pour obtenir de nouvelles connaissances, des limites de complexité améliorées et des algorithmes plus rapides pour les modèles suivants: réseaux temporels hyper, réseaux conditionnels Simples / Hyper temporels, jeux de mise à jour, jeux Muller McNaughton et jeux Mean Payoff
Fichier principal
Vignette du fichier
TH2017PESC1061.pdf (1.55 Mo) Télécharger le fichier
Origin : Version validated by the jury (STAR)
Loading...

Dates and versions

tel-01734870 , version 1 (15-03-2018)

Identifiers

  • HAL Id : tel-01734870 , version 1

Cite

Carlo Comin. Complexity in Infinite Games on Graphs and Temporal Constraint Networks. Technology for Human Learning. Université Paris-Est; Università degli studi di Trento (Trentin, Italie), 2017. English. ⟨NNT : 2017PESC1061⟩. ⟨tel-01734870⟩
152 View
109 Download

Share

Gmail Facebook Twitter LinkedIn More