KIT | KIT-Bibliothek | Impressum | Datenschutz

Complexity-theoretic aspects of expanding cellular automata

Modanese, Augusto

Abstract:
The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexity-theoretical standpoint. An XCA is a one-dimensional cellular automaton which can dynamically create new cells between existing ones. The respective polynomial-time complexity class is shown to coincide with $≤^{p}_{tt}$(NP), that is, the class of decision problems polynomial-time truth-table reducible to problems in NP. An alternative characterization based on a variant of non-deterministic Turing machines is also given. In addition, corollaries on select XCA variants are proven: XCAs with multiple accept and reject states are shown to be polynomial-time equivalent to the original XCA model. Finally, XCAs with alternative acceptance conditions are considered and classified in terms of $≤^{p}_{tt}$(NP) and the Turing machine polynomial-time class P.


Verlagsausgabe §
DOI: 10.5445/IR/1000126671
Veröffentlicht am 23.11.2020
Cover der Publikation
Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Zeitschriftenaufsatz
Publikationsjahr 2020
Sprache Englisch
Identifikator ISSN: 1567-7818, 1572-9796
KITopen-ID: 1000126671
Erschienen in Natural computing
Verlag Springer
Vorab online veröffentlicht am 10.11.2020
Nachgewiesen in Scopus
Dimensions
Web of Science
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page