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

https://hal.inria.fr/hal-01824875
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

File

 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

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

304