A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

Sequentializing cellular automata




TekijätJarkko Kari, Ville Salo, Thomas Worsch

KustantajaSpringer

Julkaisuvuosi2019

JournalNatural Computing

eISSN1572-9796

DOIhttps://doi.org/10.1007/s11047-019-09745-7

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/40800741


Tiivistelmä

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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.





Last updated on 2024-26-11 at 22:06