Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4952308 | Theoretical Computer Science | 2017 | 17 Pages |
Abstract
This article explores the computational power of bi-dimensional cellular automata acting on periodical configurations. It extends in some sense the results of a similar paper dedicated to the one-dimensional case. More precisely, we present an algorithm that computes a “minimal pattern network”, i.e. a minimal pattern and the two translation vectors it can use to tile the entire configuration. This problem is equivalent to the computation of a leader, which is one equivalence class of the cells of the periodical configuration.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Nicolas Bacquey,