On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism

Pierre-Cyrille Heam 1 Jean-Luc Joly 1
1 CASSIS - Combination of approaches to the security of infinite states systems
FEMTO-ST - Franche-Comté Électronique Mécanique, Thermique et Optique - Sciences et Technologies (UMR 6174), Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this paper we address the problem of the uniform random generation of non deterministic automata (NFA) up to isomorphism. First, we show how to use a Monte-Carlo approach to uniformly sample a NFA. Secondly, we show how to use the Metropolis-Hastings Algorithm to uniformly generate NFAs up to isomorphism. Using labeling techniques, we show that in practice it is possible to move into the modified Markov Chain efficiently, allowing the random generation of NFAs up to isomorphism with dozens of states. This general approach is also applied to several interesting subclasses of NFAs (up to isomorphism), such as NFAs having a unique initial states and a bounded output degree. Finally, we prove that for these interesting subclasses of NFAs, moving into the Metropolis Markov chain can be done in polynomial time. Promising experimental results constitute a practical contribution.
Type de document :
Communication dans un congrès
Frank Drewes. CIAA 2015, Aug 2015, Umea, Sweden. Springer, 9223, pp.12, 2015, Implementation and Application of Automata - 20th International Conference. 〈10.1007/978-3-319-22360-5_12〉
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01239735
Contributeur : Pierre-Cyrille Heam <>
Soumis le : mardi 8 décembre 2015 - 16:35:23
Dernière modification le : vendredi 6 juillet 2018 - 15:06:10
Document(s) archivé(s) le : mercredi 9 mars 2016 - 13:19:23

Fichiers

main.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Pierre-Cyrille Heam, Jean-Luc Joly. On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism. Frank Drewes. CIAA 2015, Aug 2015, Umea, Sweden. Springer, 9223, pp.12, 2015, Implementation and Application of Automata - 20th International Conference. 〈10.1007/978-3-319-22360-5_12〉. 〈hal-01239735〉

Partager

Métriques

Consultations de la notice

206

Téléchargements de fichiers

243