A single-copy minimal-time simulation of a torus of automata by a ring of automata

AbstractWe consider cellular automata on Cayley graphs and we simulate the behavior of a torus of n×m automata (nodes) by a ring of n·m automata (cells). Our simulation technique requires the neighborhood of the nodes to be preserved. We achieve this constraint by copying the contents of nodes on the cells. We consider the problem of minimizing the number of the copies. We prove that it is possible to simulate the behavior of a torus on a ring with a single copy on each cell if and only if n and m satisfy a given condition. In that case we propose a time-optimal algorithm. We thus improve a previous work done by Martin where two copies were requested. When the condition on n and m is not fulfilled one can use the previous algorithm