2026-07-20T05:24:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7797 2024-03-06T10:41:10Z ddc:004 open_access

Uniform Sampling for Networks of Automata Basset, Nicolas Mairesse, Jean Soria, Michèle Partially synchronised automata uniform sampling; recursive method Boltzmann sampling Parry measure 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nicolas Basset and Jean Mairesse and Michèle Soria 2017 Is Part Of LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2017.36 urn:nbn:de:0030-drops-77977 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.36 eng https://creativecommons.org/licenses/by/3.0/legalcode