Computer Science – Discrete Mathematics
Scientific paper
2006-04-04
Mathematical Foundations of Computer Science 2006Springer (Ed.) (28/08/2006) 190-201
Computer Science
Discrete Mathematics
Scientific paper
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.
Boyer Laurent
Poupet Victor
Theyssier Guillaume
No associations
LandOfFree
On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-500952