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 en 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
Laboratoire
Laboratoire de l'informatique du parallélisme (LIP) à l'école normale supérieure de Lyon (ENS Lyon)
Directeurs de thèse
Jacques Mazoyer et 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 à l'ENS Lyon