A4 Refereed article in a conference publication
Sequentializing cellular automata
Authors: Kari J., Salo V., Worsch T.
Editors: Jan M. Baetens, Martin Kutrib
Conference name: International Workshop on Cellular Automata and Discrete Complex Systems
Publisher: Springer Verlag
Publication year: 2018
Journal: Lecture Notes in Computer Science
Book title : Cellular Automata and Discrete Complex Systems : 24th IFIP WG 1.5 International Workshop, AUTOMATA 2018, Ghent, Belgium, June 20–22, 2018, Proceedings
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series title: Lecture Notes in Computer Science
Volume: 10875
First page : 72
Last page: 87
Number of pages: 16
ISBN: 978-3-319-92674-2
eISBN: 978-3-319-92675-9
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-92675-9_6
Web address : https://link.springer.com/chapter/10.1007/978-3-319-92675-9_6
Self-archived copy’s web address: 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.
