%0 Conference Proceedings
%T Complexity-Theoretic Aspects of Expanding Cellular Automata
%+ Institute of Theoretical Informatics
%A Modanese, Augusto
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 25th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA)
%C Guadalajara, Mexico
%Y Alonso Castillo-Ramirez
%Y Pedro P. B. de Oliveira
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-11525
%P 20-34
%8 2019-06-26
%D 2019
%R 10.1007/978-3-030-20981-0_2
%Z Computer Science [cs]Conference papers
%X 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 .
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-02312620/document
%2 https://inria.hal.science/hal-02312620/file/484947_1_En_2_Chapter.pdf
%L hal-02312620
%U https://inria.hal.science/hal-02312620
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IFIP-LNCS-11525