1 Search Results for "Busic, Ana"


Document
Probabilistic cellular automata, invariant measures, and perfect sampling

Authors: Ana Busic, Jean Mairesse, and Irene Marcovici

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


Abstract
In a probabilistic cellular automaton (PCA), the cells are updated synchronously and independently, according to a distribution depending on a finite neighborhood. A PCA can be viewed as a Markov chain whose ergodicity is investigated. A classical cellular automaton (CA) is a particular case of PCA. For a 1-dimensional CA, we prove that ergodicity is equivalent to nilpotency, and is therefore undecidable. We then propose an efficient perfect sampling algorithm for the invariant measure of an ergodic PCA. Our algorithm does not assume any monotonicity property of the local rule. It is based on a bounding process which is shown to be also a PCA.

Cite as

Ana Busic, Jean Mairesse, and Irene Marcovici. Probabilistic cellular automata, invariant measures, and perfect sampling. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 296-307, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)


Copy BibTex To Clipboard

@InProceedings{busic_et_al:LIPIcs.STACS.2011.296,
  author =	{Busic, Ana and Mairesse, Jean and Marcovici, Irene},
  title =	{{Probabilistic cellular automata, invariant measures, and perfect sampling}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{296--307},
  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.296},
  URN =		{urn:nbn:de:0030-drops-30190},
  doi =		{10.4230/LIPIcs.STACS.2011.296},
  annote =	{Keywords: probabilistic cellular automata, perfect sampling, ergodicity}
}
  • Refine by Author
  • 1 Busic, Ana
  • 1 Mairesse, Jean
  • 1 Marcovici, Irene

  • Refine by Classification

  • Refine by Keyword
  • 1 ergodicity
  • 1 perfect sampling
  • 1 probabilistic cellular automata

  • 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