On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures

Laurent Boyer
Victor Poupet
Guillaume Theyssier

Résumé

We study the notion of limit sets of cellular automata associated with probability measures (mu-limit sets). This notion was introduced by P. Kurka and A. Maass. It is a refinement of the classical notion of omega-limit sets dealing with the typical long term behavior of cellular automata. It focuses on the words whose probability of appearance does not tend to 0 as time tends to infinity (the persistent words). In this paper, we give a characterisation of the persistent language for non sensible cellular automata associated with Bernouilli measures. We also study the computational complexity of these languages. We show that the persistent language can be non-recursive. But our main result is that the set of quasi-nilpotent cellular automata (those with a single configuration in their mu-limit set) is neither recursively enumerable nor co-recursively enumerable.
Fichier principal
Vignette du fichier
boypouthe_correc.pdf (174.29 Ko) Télécharger le fichier
Loading...

Dates et versions

hal-00022186 , version 1 (04-04-2006)
hal-00022186 , version 2 (02-10-2006)

Identifiants

Citer

Laurent Boyer, Victor Poupet, Guillaume Theyssier. On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures. Slovak Society for Computer Science ; Faculty of Mathematics, Physics and Informatics, Comenius University, Bratislava, Aug 2006, Stará Lesná, pp.190-201. ⟨hal-00022186v2⟩
383 Consultations
204 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More