The state complexity of random DFAs

2013/07/02 by Berend, Daniel, Kontorovich, Aryeh
#60C05 #68Q45 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #Probability (math.PR)

paper · doi:10.48550/arxiv.1307.0720

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]×[k]×2^[n] of all such automata. We show that, with high probability, the latter is α_k n + O(√ nlog n) for a certain explicit constant α_k.

Related

• A lower bound on the state complexity of transforming two-way nondeterministic finite automata to unambiguous finite automata
• A Close Analysis of the Subset Construction
• Probabilistic automatic complexity of finite strings
• The state complexity of L² and L^k
• Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks