http://www.lirmm.fr/~poupet/
e-mail: victor.poupet [at] lirmm.fr
English Version

Recherche : thèse

Cette page est consacrée aux informations relatives à ma thèse de doctorat.

Blue Sea -

Contenu

Titre

Automates cellulaires : temps réel et voisinages

Mots-clés

Automates cellulaires, voisinages, reconnaissance de langages, dimension quelconque, temps réel, enveloppe convexe, accélération constante, accélération linéaire.

Résumé

Dans cette thèse nous nous sommes intéressés à l'importance du choix du voisinage sur les capacités algorithmiques des automates cellulaires. Nous avons travaillé en dimension quelconque en nous concentrant sur les classes de complexité correspondant au temps réel (plus petit temps nécessaire pour que l'automate ait lu le mot en entrée) et temps réel plus une constante. En effet il est connu que les voisinages sont équivalents en temps linéaire et il est donc nécessaire de considérer des temps inférieurs.

Nous avons obtenu plusieurs résultats d'équivalences de voisinages au sens du temps réel (des classes de voisinages tels que les automates fonctionnant sur ces voisinages reconnaissent les mêmes langages) et des résultats d'accélérations linéaires ou constantes selon les voisinages.

Un résumé plus détaillé (pour le dossier de soutenance) est disponible au format [pdf].

Rapport

Dernière version (03/10/08) [PDF]

Version contenant des références hypertexte. Les références ont été corrigées par rapport à la version précédente qui était disponible sur cette page web.

Informations administratives

Laboratoire

Laboratoire de l'informatique du parallélisme (LIP) à l'école normale supérieure de Lyon (ENS Lyon).

Directeurs de thèse

Jacques Mazoyer
Marianne Delorme

Jury

Bruno Durand
Etienne Grandjean (rapporteur)
Martin Kutrib
Kenichi Morita (rapporteur)
Véronique Terrier (invitée)

Date et lieu de soutenance

vendredi 8 décembre 2006
ENS Lyon
Valid XHTML 1.0 Transitional Valid CSS! Valid Konami!