Random Generation of Deterministic Acyclic Automata Using Markov Chains

DOI10.1007/978-3-642-22256-6_7zbMath1297.68109OpenAlexW73729413MaRDI QIDQ5200053

Sven De Felice, Vincent Carnino

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)

Related Items

On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata

Uses Software

• LANGAGE

Cites Work

• Unnamed Item
• Enumeration and random generation of accessible automata
• Minimisation of acyclic deterministic automata in linear time
• A calculus for the random generation of labelled combinatorial structures
• Characterization of Glushkov automata
• Random generation of DFAs
• Acyclic automata and small expressions using multi-tilde-bar operators
• Parametric random generation of deterministic tree automata
• Generating connected acyclic digraphs uniformly at random
• Exact enumeration of acyclic deterministic automata
• Random Generation of Directed Acyclic Graphs
• EXACT GENERATION OF MINIMAL ACYCLIC DETERMINISTIC FINITE AUTOMATA
• Small Extended Expressions for Acyclic Automata
• Boltzmann Samplers for the Random Generation of Combinatorial Structures