KIT | KIT-Bibliothek | Impressum | Datenschutz

Sequentializing cellular automata [in press]

Kari, J.; Salo, V.; Worsch, T.

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.

Open Access Logo


Verlagsausgabe §
DOI: 10.5445/IR/1000095856
Veröffentlicht am 26.06.2019
Originalveröffentlichung
DOI: 10.1007/s11047-019-09745-7
Coverbild
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Jahr 2019
Sprache Englisch
Identifikator ISSN: 1567-7818, 1572-9796
KITopen-ID: 1000095856
Erschienen in Natural computing
Vorab online veröffentlicht am 01.06.2019
Schlagworte Cellular automata, Closing, Sequentialization
Nachgewiesen in Scopus
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page