The state complexity of random DFAs

DOI10.1016/J.TCS.2016.09.012MaRDI QIDQ338393zbMATH OpenOpenAlexFDO

Authors Daniel Berend, 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)

Abstract: The state complexity of a Deterministic Finite-state automaton (DFA) is the number of states in its minimal equivalent DFA. We study the state complexity of random $n$-state DFAs over a $k$-symbol alphabet, drawn uniformly from the set $[n{]}^{[n]imes[k]}imes{2}^{[n]}$ of all such automata. We show that, with high probability, the latter is $alph{a}_{k}n+O(sqrtnlogn)$ for a certain explicit constant $alph{a}_k$.

Recommendations

• scientific article; zbMATH DE number 2201359
• The state complexity of \(L^{2}\) and \(L^k\)
• On the average state and transition complexity of finite languages
• State complexity of power
• scientific article; zbMATH DE number 2201360

Cites work

• scientific article; zbMATH DE number 3427224 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1253984 (Why is no real title available?)
• scientific article; zbMATH DE number 2068873 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Asymptotic enumeration of minimal automata
• Balls and bins: A study in negative dependence
• Enumeration and random generation of accessible automata
• Limit distributions of certain characteristics of random automaton graphs
• Lower bounds on learning random structures with statistical queries
• On Spreading a Rumor
• On distributions related to transitive closures of random finite mappings
• Random generation of DFAs
• Universal kernel-based learning with applications to regular languages

Cited in

(9)

• Random deterministic automata
• Diameter and stationary distribution of random \(r\)-out digraphs
• On the meeting of random walks on random DFA
• The graph structure of a deterministic automaton chosen at random
• Asymptotic estimation of the average number of terminal states in DAWGs
• Learning a Random DFA from Uniform Strings and State Information
• scientific article; zbMATH DE number 1747444 (Why is no real title available?)
• scientific article; zbMATH DE number 2201360 (Why is no real title available?)
• scientific article; zbMATH DE number 3972194 (Why is no real title available?)

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

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