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 sweep of a bijective rule from left to right over an infinite tape. Such cellular automata are necessarily left-closing, and they move at least as much information to the left as they move information to the right.
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Zeitschriftenaufsatz |
| Publikationsmonat/-jahr | 12.2020 |
| Sprache | Englisch |
| Identifikator | ISSN: 1567-7818, 1572-9796 KITopen-ID: 1000095856 |
| Erschienen in | Natural computing |
| Verlag | Springer |
| Band | 19 |
| Heft | 4 |
| Seiten | 759–772 |
| Vorab online veröffentlicht am | 01.06.2019 |
| Schlagwörter | Cellular automata, Closing, Sequentialization |
| Nachgewiesen in | OpenAlex Dimensions Scopus |