The state complexity of random DFAs

DOI10.1016/j.tcs.2016.09.012zbMath1353.68159arXiv1307.0720OpenAlexW2963359525MaRDI QIDQ338393

Daniel Berend, Leonid (Aryeh) Kontorovich

Publication date: 4 November 2016

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

Full work available at URL: https://arxiv.org/abs/1307.0720

zbMATH Keywords

randomDFAminimaldeterministic finite-state automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (2)

Random Deterministic Automata ⋮ Diameter and stationary distribution of random \(r\)-out digraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Enumeration and random generation of accessible automata
• On distributions related to transitive closures of random finite mappings
• Random generation of DFAs
• Limit distributions of certain characteristics of random automaton graphs
• Asymptotic enumeration of Minimal Automata
• On Spreading a Rumor
• Balls and bins: A study in negative dependence
• Lower Bounds on Learning Random Structures with Statistical Queries

This page was built for publication: The state complexity of random DFAs