Sampling different kinds of acyclic automata using Markov chains

DOI10.1016/J.TCS.2012.04.025MaRDI QIDQ442144zbMATH OpenOpenAlexFDO

Authors Vincent Carnino, Sven De Felice

Publication date 9 August 2012

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2012.04.025

zbMATH Keywords

Markov chainsminimal automatarandom automata generation

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Review text

This paper is concerned with the random generation of (minimal) acyclic deterministic finite-state automata. Two algorithms are presented: (a) to generate acyclic automata, and (b) to generate minimal acyclic automata. Both algorithms iteratively change some transitions in an initial \(n\)-state (minimal) acyclic automaton, while keeping the same state space, acyclicity and, if applicable, minimality. The modified transitions are selected randomly. The authors prove that for both algorithms, the Markov chain describing the random amendments is ergodic and symmetric. By standard results in Markov chain theory it follows that the stationary distribution of the Markov chain is uniform.

Recommendations

• Random generation of deterministic acyclic automata using Markov chains
• Sampling automata and programs
• Sampling a two-way finite automaton
• Accessible and deterministic automata: enumeration and Boltzmann samplers
• Markov chains and unambiguous automata
• Random generation of deterministic acyclic automata using the recursive method
• scientific article; zbMATH DE number 7204953
• Multi-parametric classification of automaton Markov models based on the sequences they generate
• Efficient modelling and generation of Markov automata
• On sampling with Markov chains

Cites work

• A calculus for the random generation of labelled combinatorial structures
• Acyclic automata and small expressions using multi-tilde-bar operators
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Characterization of Glushkov automata
• Enumeration and random generation of accessible automata
• Exact enumeration of acyclic deterministic automata
• EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
• Generating connected acyclic digraphs uniformly at random
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1045407 (Why is no real title available?)
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Minimisation of acyclic deterministic automata in linear time
• Parametric random generation of deterministic tree automata
• Random generation of DFAs
• Random Generation of Directed Acyclic Graphs
• Small Extended Expressions for Acyclic Automata

Cited in

(5)

• Asymptotic enumeration of compacted binary trees of bounded right height
• Markov chain algorithms for generating sets uniformly at random
• On the uniform random generation of non deterministic automata up to isomorphism
• Random generation of deterministic acyclic automata using the recursive method
• Random generation of deterministic acyclic automata using Markov chains

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: Sampling different kinds of acyclic automata using Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442144)