Skip to Main content Skip to Navigation
Conference papers

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 metadata

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

469010_1_En_6_Chapter.pdf
Files produced by the author(s)

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

375

Files downloads

3