Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [10 references]  Display  Hide  Download
Contributor : Cyril Nicaud Connect in order to contact the contributor
Submitted on : Saturday, July 6, 2013 - 1:09:39 PM
Last modification on : Friday, September 16, 2022 - 1:49:45 PM
Long-term archiving on: : Monday, October 7, 2013 - 2:30:11 AM


Files produced by the author(s)



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⟩



Record views


Files downloads