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

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

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

• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1045407 (Why is no real title available?)
• 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
• EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
• Enumeration and random generation of accessible automata
• Exact enumeration of acyclic deterministic automata
• Generating connected acyclic digraphs uniformly at random
• 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 Directed Acyclic Graphs
• Random generation of DFAs
• Small Extended Expressions for Acyclic Automata

Cited in

(5)

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

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)