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

Search Results

Documents authored by Soria, Michèle

Uniform Sampling for Networks of Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message