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.CONCUR.2017.36
URN: urn:nbn:de:0030-drops-77977
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7797/
Go to the corresponding LIPIcs Volume Portal

Basset, Nicolas ; Mairesse, Jean ; Soria, Michèle

Uniform Sampling for Networks of Automata

pdf-format:
LIPIcs-CONCUR-2017-36.pdf (0.6 MB)

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.

BibTeX - Entry

@InProceedings{basset_et_al:LIPIcs:2017:7797,
  author =	{Nicolas Basset and Jean Mairesse and Mich{\`e}le Soria},
  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 =	{Roland Meyer and Uwe Nestmann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7797},
  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}
}

Keywords: Partially synchronised automata, uniform sampling; recursive method, Boltzmann sampling, Parry measure
Collection: 28th International Conference on Concurrency Theory (CONCUR 2017)
Issue Date: 2017
Date of publication: 01.09.2017

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