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
.
https://hal.inria.fr/hal-02312620 Contributor : Hal IfipConnect 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
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⟩