Sequentializing Cellular Automata

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 left-to-right sweep of a bijective rule from left to right over an infinite tape.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download
Contributor : Hal Ifip <>
Submitted on : Wednesday, June 27, 2018 - 4:37:55 PM
Last modification on : Wednesday, August 29, 2018 - 11:02:02 AM
Long-term archiving on: Thursday, September 27, 2018 - 4:32:51 AM


 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document


Distributed under a Creative Commons Attribution 4.0 International License



Jarkko Kari, Ville Salo, Thomas Worsch. Sequentializing Cellular Automata. 24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.72-87, ⟨10.1007/978-3-319-92675-9_6⟩. ⟨hal-01824875⟩



Record views