Thèse



J'ai effectué ma thèse en cotutelle entre l'Institut National Polytechnique de Lorraine (INPL), à Nancy, et City University of Hong Kong à Hong Kong. Mon laboratoire d'accueil à Nancy a été le Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA, UMR7503), où j'ai travaillé au sein des équipes PROTHEO et CALLIGRAMME.


Titre: Résultats de Complétude et Caractérisations Syntaxiques de Classes de Complexité sur des Structures Arbitraires
Soutenue le: 15 décembre 2004, à Hong Kong
Dirigée par: Dr. Olivier Bournez, chargé de recherches INRIA au LORIA

Pr. Jean-Yves Marion, professeur à l'INPL

Pr. Felipe Cucker, professeur à City University of Hong Kong
Jury: Dr. Olivier Bournez (LORIA)

Dr. Siu Wing Cheng (Hong Kong University of Science and Technology)

Pr. Felipe Cucker (City University of Hong Kong)

Dr. Mordecai Golin (Hong Kong University of Science and Technology)

Pr. Jean-Yves Marion (INPL, LORIA)

Dr. DingXuan Zhou (City University of Hong Kong)
Après avis de: Dr. Mordecai Golin (Hong Kong University of Science and Technology)

Pr. Pascal Koiran (Ecole Normale Supérieure de Lyon)

Pr. Michel de Rougemont (Université Paris II)

Dr. DingXuan Zhou (City University of Hong Kong)
Résumé: Nous nous plaçons dans le modèle de calcul BSS sur des structures arbitraires. Nous présentons de nouveaux résultats de complétude concernant des problèmes géométriques sur les nombres réels avec addition et ordre. Nous présentons aussi plusieurs caractérisations de classes de complexité indépendantes du modèle de calcul sous-jacent. Nous étendons des résultats de Grädel, Gurevich et Meer en complexité descriptive, qui caractérisent les problèmes de décisions calculables en temps polynomial déterministe et non-déterministe en termes de logique sur des structures métafinies. Nous étendons des résultats de Bellantoni et Cook pour caractériser les fonctions calculables en temps polynomial séquentiel, et de Leivant et Marion pour caractéeriser les fonctions calculables en temps polynomial parallèle, en termes d'algèbres de fonctions récursives. Nous présentons également des caractérisations de fonctions calculables dans la hiérarchie polynomiale et en temps polynomial alternant.
Mots clés: modèle de calcul BSS, complexité algébrique, complexité descriptive, complexité implicite, logique, algèbres de fonctions récursives.


télécharger (postscript, pdf)