Sequentializing cellular automata
: Kari J., Salo V., Worsch T.
: Jan M. Baetens, Martin Kutrib
: International Workshop on Cellular Automata and Discrete Complex Systems
Publisher: Springer Verlag
: 2018
: Lecture Notes in Computer Science
: Cellular Automata and Discrete Complex Systems : 24th IFIP WG 1.5 International Workshop, AUTOMATA 2018, Ghent, Belgium, June 20–22, 2018, Proceedings
: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
: Lecture Notes in Computer Science
: 10875
: 72
: 87
: 16
: 978-3-319-92674-2
: 978-3-319-92675-9
: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-92675-9_6
: https://link.springer.com/chapter/10.1007/978-3-319-92675-9_6
: https://arxiv.org/abs/1802.06668
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.
