A1 Refereed original research article in a scientific journal

Sequentializing cellular automata




AuthorsJarkko Kari, Ville Salo, Thomas Worsch

PublisherSpringer

Publication year2019

JournalNatural Computing

eISSN1572-9796

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

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/40800741


Abstract

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.


Downloadable publication

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