Portal de Periódicos da CAPES

Complexity-Theoretic Aspects of Expanding Cellular Automata

2019; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-030-20981-0_2

1611-3349

Augusto Modanese,

Computability, Logic, AI Algorithms

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 .