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.