Random generation of deterministic acyclic automata using Markov chains

DOI10.1007/978-3-642-22256-6_7MaRDI QIDQ5200053zbMATH OpenOpenAlexFDO

Authors Vincent Carnino, Sven De Felice

Publication date 29 July 2011

Published in Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22256-6_7

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• Sampling different kinds of acyclic automata using Markov chains
• Markov chain algorithms for generating sets uniformly at random
• Random generation of deterministic acyclic automata using the recursive method
• Enumeration and random generation of possibly incomplete deterministic automata
• Distribution of the number of accessible states in a random deterministic automaton

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 1045407 (Why is no real title available?)
• 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

(15)

• Random generation of DFAs
• Parametric random generation of deterministic tree automata
• Distribution of the number of accessible states in a random deterministic automaton
• Markov chain algorithms for generating sets uniformly at random
• On the uniform random generation of non deterministic automata up to isomorphism
• Random generation and enumeration of accessible deterministic real-time pushdown automata
• Enumeration and random generation of possibly incomplete deterministic automata
• REGAL: A Library to Randomly and Exhaustively Generate Automata
• Accessible and deterministic automata: enumeration and Boltzmann samplers
• Random Generation of Deterministic Tree (Walking) Automata
• scientific article; zbMATH DE number 4047127 (Why is no real title available?)
• Sampling different kinds of acyclic automata using Markov chains
• Random generation of deterministic acyclic automata using the recursive method
• Random generation of source vectors with a fixed preponderant property
• Enumeration and random generation of accessible automata

Describes a project that uses

Uses Software

• LANGAGE

This page was built for publication: Random generation of deterministic acyclic automata using Markov chains

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