Automates cellulaires: dynamique directionnelle et asymptotique typique / par Martin Delacourt

Auteur: Delacourt, Martin (1985-) - AuteurAuteur secondaire : Durand, Bruno - Directeur de thèse ; Poupet, Victor - Directeur de thèseCollectivité secondaire: Université de Provence - Etablissement de soutenanceType de document: ThèseLangue: françaisPays: FranceÉditeur: [S.l.] : [s.n.], 2011Description: 1 vol. (XIV-125 p.) : fig. ; 30 cmRésumé: Les automates cellulaires sont à la fois un modèle de calcul parallèle, un système complexe et un système dynamique. Ils fonctionnent de manière synchrone et en temps discret, leur particularité est que les fonctions qu'ils définissent sont issues de l'application simultanée, en tout point de l'espace, d'une règle d'évolution locale. L'ensemble limite est un objet classique des systèmes dynamiques, c'est l'ensemble des états que le système peut atteindre arbitrairement tard. Il a été très étudié dans le cadre des automates cellulaires, et les résultats sont nombreux. Parmi ces résultats, un théorème de Rice démontré par Jarkko Kari dit que toute propriété des ensembles limites est indécidable. Dans ce mémoire, on ne s'intéresse plus à l'ensemble limite traditionnel, mais à une variante pour laquelle on utilise une mesure sur l'espace des entrées, sélectionnant ainsi les comportements susceptibles d'apparaître arbitrairement tard et souvent. Ce nouvel ensemble, que l'on nomme ensemble mu-limite, a été introduit en 2000 par Petr Kurka et Alejandro Maass. La plupart des résultats sur les ensembles limites ne se transposent pas naturellement. On étudie la famille des ensembles mu-limites d'automates cellulaires. On montre que sous certaines contraintes sur la dynamique, l'ensemble mu-limite peut être entièrement décrit. On classe ainsi les automates en fonction de ces contraintes. Dans le cas général, on montre l'existence d'automates cellulaires ayant comme ensembles mu-limites un grand nombre d'ensembles complexes. On finit par montrer un théorème de Rice pour les ensembles mu-limites d'automates cellulaires: tout propriété non triviale de ces ensembles est indécidable.Bibliographie: Bibliogr. p. 121-124. Index.Thèse: Thèse de doctorat en informatique, soutenue en 2011, organisme : Aix-Marseille 1 Sujets MSC: 37B15 Dynamical systems and ergodic theory -- Topological dynamics -- Cellular automata
68Q80 Computer science -- Theory of computing -- Cellular automata
97A70 Mathematics education - General, mathematics and education -- Theses and postdoctoral theses
En-ligne: Thèse.fr
Location Call Number Status Date Due
Salle S 06507-01 / Thèses DEL (Browse Shelf) Available

Bibliogr. p. 121-124. Index

Thèse de doctorat informatique 2011 Aix-Marseille 1

Les automates cellulaires sont à la fois un modèle de calcul parallèle, un système complexe et un système dynamique. Ils fonctionnent de manière synchrone et en temps discret, leur particularité est que les fonctions qu'ils définissent sont issues de l'application simultanée, en tout point de l'espace, d'une règle d'évolution locale. L'ensemble limite est un objet classique des systèmes dynamiques, c'est l'ensemble des états que le système peut atteindre arbitrairement tard. Il a été très étudié dans le cadre des automates cellulaires, et les résultats sont nombreux. Parmi ces résultats, un théorème de Rice démontré par Jarkko Kari dit que toute propriété des ensembles limites est indécidable. Dans ce mémoire, on ne s'intéresse plus à l'ensemble limite traditionnel, mais à une variante pour laquelle on utilise une mesure sur l'espace des entrées, sélectionnant ainsi les comportements susceptibles d'apparaître arbitrairement tard et souvent. Ce nouvel ensemble, que l'on nomme ensemble mu-limite, a été introduit en 2000 par Petr Kurka et Alejandro Maass. La plupart des résultats sur les ensembles limites ne se transposent pas naturellement. On étudie la famille des ensembles mu-limites d'automates cellulaires. On montre que sous certaines contraintes sur la dynamique, l'ensemble mu-limite peut être entièrement décrit. On classe ainsi les automates en fonction de ces contraintes. Dans le cas général, on montre l'existence d'automates cellulaires ayant comme ensembles mu-limites un grand nombre d'ensembles complexes. On finit par montrer un théorème de Rice pour les ensembles mu-limites d'automates cellulaires: tout propriété non triviale de ces ensembles est indécidable

Disponible au format pdf : 1 fichier (1,4 Mo)

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |