Complexity classes on spatially periodic Cellular Automata

Author Nicolas Bacquey



PDF
Thumbnail PDF

File

LIPIcs.STACS.2014.112.pdf
  • Filesize: 0.57 MB
  • 13 pages

Document Identifiers

Author Details

Nicolas Bacquey

Cite AsGet BibTex

Nicolas Bacquey. Complexity classes on spatially periodic Cellular Automata. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 112-124, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
https://doi.org/10.4230/LIPIcs.STACS.2014.112

Abstract

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.
Keywords
  • Language recognition
  • cyclic languages
  • computable functions
  • algorithms on Cellular Automata
  • linear space
  • polynomial time
  • density classification p

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail