1 Search Results for "Fates, Nazim"

Document
DOI: 10.4230/LIPIcs.STACS.2011.284
Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision

Authors: Nazim Fates

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
The density classification problem consists in using a binary cellular automaton (CA) to decide whether an initial configuration contains more 0s or 1s. This problem is known for having no exact solution in the case of binary, deterministic, one-dimensional CA. Stochastic cellular automata have been studied as an alternative for solving the problem. This paper is aimed at presenting techniques to analyse the behaviour of stochastic CA rules, seen as a ``blend'' of deterministic CA rules. Using analytical calculations and numerical simulations, we analyse two previously studied rules and present a new rule. We estimate their quality of classification and their average time of classification. We show that the new rule solves the problem with an arbitrary precision. From a practical point of view, this rule is effective and exhibits a high quality of classification, even when the simulation time is kept small.
Cite as

Nazim Fates. Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 284-295, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{fates:LIPIcs.STACS.2011.284,
  author =	{Fates, Nazim},
  title =	{{Stochastic Cellular Automata Solve the Density Classification Problem with an Arbitrary Precision}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{284--295},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.284},
  URN =		{urn:nbn:de:0030-drops-30187},
  doi =		{10.4230/LIPIcs.STACS.2011.284},
  annote =	{Keywords: stochastic and probabilistic cellular automata, density classification problem, models of spatially distributed computing, stochastic process}
}
  • Refine by Author
  • 1 Fates, Nazim

  • Refine by Classification

  • Refine by Keyword
  • 1 density classification problem
  • 1 models of spatially distributed computing
  • 1 stochastic and probabilistic cellular automata
  • 1 stochastic process

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2011

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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact