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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00841862
Contributor : Cyril Nicaud <>
Submitted on : Sunday, July 7, 2013 - 11:17:13 AM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Tuesday, October 8, 2013 - 2:35:12 AM

File

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

Identifiers

Citation

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⟩

Share

Metrics

Record views

218

Files downloads

261