Random Generation of Deterministic Acyclic Automata Using the Recursive Method

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [10 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00841835
Contributor : Cyril Nicaud <>
Submitted on : Saturday, July 6, 2013 - 1:09:39 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Monday, October 7, 2013 - 2:30:11 AM

File

Random_Generation_of_Determini...
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

251

Files downloads

152