DROPS

Document

DOI: 10.4230/LIPIcs.CONCUR.2017.36

Uniform Sampling for Networks of Automata

Authors: Nicolas Basset, Jean Mairesse, and Michèle Soria

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract

We call network of automata a family of partially synchronised automata, i.e. a family of deterministic automata which are synchronised via shared letters, and evolve independently otherwise. We address the problem of uniform random sampling of words recognised by a network of automata. To that purpose, we define the reduced automaton of the model, which involves only the product of the synchronised part of the component automata. We provide uniform sampling algorithms which are polynomial with respect to the size of the reduced automaton, greatly improving on the best known algorithms. Our sampling algorithms rely on combinatorial and probabilistic methods and are of three different types: exact, Boltzmann and Parry sampling.

Cite as

Nicolas Basset, Jean Mairesse, and Michèle Soria. Uniform Sampling for Networks of Automata. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{basset_et_al:LIPIcs.CONCUR.2017.36,
  author =	{Basset, Nicolas and Mairesse, Jean and Soria, Mich\`{e}le},
  title =	{{Uniform Sampling for Networks of Automata}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.36},
  URN =		{urn:nbn:de:0030-drops-77977},
  doi =		{10.4230/LIPIcs.CONCUR.2017.36},
  annote =	{Keywords: Partially synchronised automata, uniform sampling; recursive method, Boltzmann sampling, Parry measure}
}

Document

DOI: 10.4230/LIPIcs.STACS.2011.296

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.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}
}

Search Results

Documents authored by Mairesse, Jean

Uniform Sampling for Networks of Automata

Abstract

Cite as

Probabilistic cellular automata, invariant measures, and perfect sampling

Abstract

Cite as

Thanks for your feedback!

Could not send message