Thèse d'Olivier Bournez

Titre:

Complexité algorithmique des systèmes dynamiques continus et hybrides.

(soutenue le 18 Janvier 1999)

Distinctions:

Cette thèse a obtenu un des deux accessits du prix de thèse SPECIF 1999.
Cette thèse a été distinguée par l' Association Francaise d'Informatique Théorique (AFIT).

Résumé:

Cette thèse présente une étude de la complexité algorithmique de la vérification automatique de propriétés pour les systèmes dynamiques continus et hybrides.
Dans un premier temps nous étudions la décidabilité de la vérification automatique de propriétés des systèmes dynamiques à espace continu: nous prouvons tout d'abord l'indécidabilité du problème de la stabilité des systèmes dynamiques linéaires seuillés, puis nous étudions la frontière entre décidabilité et indécidabilité pour les systèmes de basses dimensions en discutant l'existence d'un algorithme pour décider la mortalité des matrices deux par deux.
Dans un second temps, nous étudions la représentation des polyèdres par leurs sommets: nous proposons plusieurs représentations pour les polyèdres orthogonaux et prouvons que ces représentations permettent une réalisation efficace des algorithmes classiques de vérification automatique. Nous généralisons ensuite ces représentations aux polyèdres manipulés par les algorithmes de vérification de propriétés des automates temporisés.
Enfin, nous présentons une caractérisation complète de la puissance de calcul d'une classe particulière de systèmes dynamiques à espace et à temps continus: nous prouvons que la puissance de calcul des systèmes dynamiques définis par une équation différentielle constante par morceaux se relie aux classes de langages de la hiérarchie hyperarithmétique.

Téléchargement:

Fichier .ps.gz or Fichier .pdf

Click herefor an english traduction of this web page english.gif