| Article Id: |
 |
hal-00451727, version 2 |
|
|
| : |
|
arXiv:1001.5471 |
|
|
| Subject: |
|
Computer Science/Discrete Mathematics
|
|
|
| Title: |
|
Bulking II: Classifications of Cellular Automata |
|
|
| Author(s): |
|
Marianne Delorme1, Jacques Mazoyer1, Nicolas Ollinger2, Guillaume Theyssier3 |
|
|
| Laboratory: |
|
| 1: |
LIP - Laboratoire de l'Informatique du Parallélisme |
|
| 2: |
LIF - Laboratoire d'informatique Fondamentale de Marseille |
|
| 3: |
LAMA - Laboratoire de Mathématiques |
|
|
|
| Abstract: |
|
This paper is the second part of a series of two papers dealing with bulking: a way to define quasi-order on cellular automata by comparing space-time diagrams up to rescaling. In the present paper, we introduce three notions of simulation between cellular automata and study the quasi-order structures induced by these simulation relations on the whole set of cellular automata. Various aspects of these quasi-orders are considered (induced equivalence relations, maximum elements, induced orders, etc) providing several formal tools allowing to classify cellular automata. |
|
|
| Fulltext language: |
|
English |
|
|
|
| Keyword(s): |
|
cellular automata – bulking – grouping – classification |
|
|
|
Export this paper
