Random Generation of Deterministic Acyclic Automata Using the Recursive Method - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2013

Random Generation of Deterministic Acyclic Automata Using the Recursive Method

Résumé

In this article, we propose a uniform random generator for accessible deterministic acyclic automata with n states, which is based on the recursive method. The generator has a preprocessing that requires O(n3) arithmetic operations, and, once it is done, can generate acyclic automata using O(n) arithmetic operations for each sample. We also propose a lazy version of the algorithm that takes advantage of the typical shape of random acyclic automata to reduce experimentally the preprocessing. Using this algorithm, we provide some statistics on acyclic automata with up to 1000 states.
Fichier principal
Vignette du fichier
Random_Generation_of_Deterministic_Acyclic_Automata_Using_the_Recursive_Method.pdf (205.2 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00841835 , version 1 (06-07-2013)

Identifiants

Citer

Sven de Felice, Cyril Nicaud. Random Generation of Deterministic Acyclic Automata Using the Recursive Method. 8th International Computer Science Symposium in Russia (CSR'13), 2013, Russia. pp.88-99, ⟨10.1007/978-3-642-38536-0_8⟩. ⟨hal-00841835⟩
103 Consultations
122 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More