Random generation of DFAs

DOI10.1016/j.tcs.2004.03.072zbMath1078.68078OpenAlexW1969958990MaRDI QIDQ1763712

Thomas Paranthoën, Jean-Marc Champarnaud

Publication date: 22 February 2005

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

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

zbMATH Keywords

\(m\)-ary treesCatalan familiesRandom generationComplete deterministic automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

The state complexity of random DFAs ⋮ Random Deterministic Automata ⋮ On the Uniform Random Generation of Non Deterministic Automata Up to Isomorphism ⋮ Random Generation and Enumeration of Accessible Deterministic Real-Time Pushdown Automata ⋮ Sampling different kinds of acyclic automata using Markov chains ⋮ Parametric random generation of deterministic tree automata ⋮ Enumeration and generation with a string automata representation ⋮ On the average state and transition complexity of finite languages ⋮ Enumeration and random generation of accessible automata ⋮ Random Generation of Deterministic Acyclic Automata Using Markov Chains ⋮ Random Generation of Deterministic Tree (Walking) Automata

Cites Work

• Catalan numbers, their generalization, and their uses
• Lattice paths not touching a given boundary
• A Census of Finite Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item