Sampling different kinds of acyclic automata using Markov chains
Résumé
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.
Domaines
Mathématique discrète [cs.DM]
Fichier principal
Sampling_different_kinds_of_acyclic_automata_using_Markov_chains.pdf (206.05 Ko)
Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)