Skip to Main content Skip to Navigation
Conference papers

Complexity-Theoretic Aspects of Expanding Cellular Automata

Abstract : The expanding cellular automata (XCA) variant of cellular automata is investigated and characterized from a complexity-theoretical standpoint. The respective polynomial-time complexity class is shown to coincide with , that is, the class of decision problems polynomial-time truth-table reducible to problems in . 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. Meanwhile, XCAs with diverse acceptance behavior are classified in terms of and the Turing machine polynomial-time class .
Document type :
Conference papers
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Friday, October 11, 2019 - 11:34:10 AM
Last modification on : Friday, October 11, 2019 - 11:39:23 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Augusto Modanese. Complexity-Theoretic Aspects of Expanding Cellular Automata. 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2019, Guadalajara, Mexico. pp.20-34, ⟨10.1007/978-3-030-20981-0_2⟩. ⟨hal-02312620⟩



Record views


Files downloads