Skip to Main content Skip to Navigation
Conference papers

Random Generation of Deterministic Acyclic Automata Using Markov Chains

Abstract : In this article we propose an algorithm, based on Markov chain techniques, to generate random automata that are deterministic, accessible and acyclic. The distribution of the output approaches the uniform distribution on n-state such automata. We then show how to adapt this algorithm in order to generate minimal acyclic automata with n states almost uniformly.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Cyril Nicaud Connect in order to contact the contributor
Submitted on : Sunday, July 7, 2013 - 11:17:13 AM
Last modification on : Saturday, January 15, 2022 - 3:58:51 AM
Long-term archiving on: : Tuesday, October 8, 2013 - 2:35:12 AM


Files produced by the author(s)



Vincent Carnino, Sven de Felice. Random Generation of Deterministic Acyclic Automata Using Markov Chains. Implementation and Application of Automata - 16th International Conference, (CIAA'11), 2011, Blois, France. pp.65-75, ⟨10.1007/978-3-642-22256-6_7⟩. ⟨hal-00841862⟩



Record views


Files downloads