Asymptotic enumeration of Minimal Automata
classification
💻 cs.FL
math.CO
keywords
automataminimalasymptoticdistributionaccessiblealphabetarbitrarybinomial
read the original abstract
We determine the asymptotic proportion of minimal automata, within n-state accessible deterministic complete automata over a k-letter alphabet, with the uniform distribution over the possible transition structures, and a binomial distribution over terminal states, with arbitrary parameter b. It turns out that a fraction ~ 1-C(k,b) n^{-k+2} of automata is minimal, with C(k,b) a function, explicitly determined, involving the solution of a transcendental equation.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.