Sampling different kinds of acyclic automata using Markov chains

DOI10.1016/j.tcs.2012.04.025zbMath1276.68090OpenAlexW2034145883MaRDI QIDQ442144

Sven De Felice, Vincent Carnino

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)

Related Items (2)

On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Asymptotic enumeration of compacted binary trees of bounded right height

Uses Software

• LANGAGE

Cites Work

• Unnamed Item
• Unnamed Item
• 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

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