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

https://hal.inria.fr/hal-02312620
Contributor : Hal Ifip <>
Submitted on : Friday, October 11, 2019 - 11:34:10 AM
Last modification on : Friday, October 11, 2019 - 11:39:23 AM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

56