Sampling different kinds of acyclic automata using Markov chains

Abstract : We propose algorithms that use Markov chain techniques to generate acyclic automata uniformly at random. We first consider deterministic, accessible and acyclic automata, then focus on the class of minimal acyclic automata. In each case we explain how to define random local transformations that describe an ergodic and symmetric Markov chain; the distribution of the automaton obtained after T random steps in this Markov chain tends to the uniform distribution as T tends to infinity.
Document type :
Journal articles
Complete list of metadatas

https://hal-upec-upem.archives-ouvertes.fr/hal-00841870
Contributor : Cyril Nicaud <>
Submitted on : Saturday, July 6, 2013 - 1:21:14 PM
Last modification on : Friday, April 12, 2019 - 10:18:03 AM
Long-term archiving on : Monday, October 7, 2013 - 2:40:12 AM

File

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

Identifiers

Citation

Vincent Carnino, Sven de Felice. Sampling different kinds of acyclic automata using Markov chains. Theoretical Computer Science, Elsevier, 2012, 450 (1), pp.31-42. ⟨10.1016/j.tcs.2012.04.025⟩. ⟨hal-00841870⟩

Share

Metrics

Record views

242

Files downloads

168