KIT | KIT-Bibliothek | Impressum | Datenschutz

Sequentializing cellular automata

Kari, Jarkko; Salo, Ville; Worsch, Thomas 1
1 Karlsruher Institut für Technologie (KIT)

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.


Verlagsausgabe §
DOI: 10.5445/IR/1000095856
Originalveröffentlichung
DOI: 10.1007/s11047-019-09745-7
Scopus
Zitationen: 1
Dimensions
Zitationen: 1
Cover der Publikation
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 Scopus
Dimensions
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page