License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.112
URN: urn:nbn:de:0030-drops-44519
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4451/
Go to the corresponding LIPIcs Volume Portal

Bacquey, Nicolas

Complexity classes on spatially periodic Cellular Automata

pdf-format:
9.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{bacquey:LIPIcs:2014:4451,
  author =	{Nicolas Bacquey},
  title =	{{Complexity classes on spatially periodic Cellular Automata}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{112--124},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4451},
  URN =		{urn:nbn:de:0030-drops-44519},
  doi =		{10.4230/LIPIcs.STACS.2014.112},
  annote =	{Keywords: Language recognition, cyclic languages, computable functions, algorithms on Cellular Automata, linear space, polynomial time, density classification p}
}

Keywords: Language recognition, cyclic languages, computable functions, algorithms on Cellular Automata, linear space, polynomial time, density classification p
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI