2026-07-22T17:54:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:4451 2024-03-06T10:35:03Z ddc:004 open_access

Complexity classes on spatially periodic Cellular Automata Bacquey, Nicolas Language recognition cyclic languages computable functions algorithms on Cellular Automata linear space polynomial time density classification p This article deals with cellular automata (CA) working over periodic configurations, as opposed to standard CA, where the initial configuration is bounded by persistent symbols. We study the capabilities of language recognition and computation of functions over such automata, as well as the complexity classes they define over languages and functions. We show that these new complexity classes coincide with the standard ones starting from polynomial time. As a by-product, we present a CA that solves a somehow relaxed version of the density classification problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Bacquey 2014 Is Part Of LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2014.112 urn:nbn:de:0030-drops-44519 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.112 eng https://creativecommons.org/licenses/by/3.0/legalcode