A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Sequentializing cellular automata
Tekijät: Jarkko Kari, Ville Salo, Thomas Worsch
Kustantaja: Springer
Julkaisuvuosi: 2019
Journal: Natural Computing
eISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-019-09745-7
Rinnakkaistallenteen osoite: https://research.utu.fi/converis/portal/detail/Publication/40800741
We study the problem of sequentializing a cellular automaton without introducing any intermediate states, and only performing reversible permutations on the tape. We give a decidable characterization of cellular automata which can be written as a single sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right.
Ladattava julkaisu This is an electronic reprint of the original article. |