Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
437518 | Theoretical Computer Science | 2011 | 25 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics