Uniform sampling for networks of automata - Sorbonne Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2017

Uniform sampling for networks of automata

Nicolas Basset
  • Fonction : Auteur
  • PersonId : 772554
  • IdRef : 191360848
Jean Mairesse
Michèle Soria

Résumé

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.
Fichier non déposé

Dates et versions

hal-01545936 , version 1 (23-06-2017)

Identifiants

  • HAL Id : hal-01545936 , version 1

Citer

Nicolas Basset, Jean Mairesse, Michèle Soria. Uniform sampling for networks of automata. CONCUR 2017 28th International Conference on Concurrency Theory, Sep 2017, Berlin, Germany. ⟨hal-01545936⟩
159 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More