pith. sign in

arxiv: 1109.5683 · v1 · pith:VPDSJ4MYnew · submitted 2011-09-26 · 💻 cs.FL · math.CO

Asymptotic enumeration of Minimal Automata

classification 💻 cs.FL math.CO
keywords automataminimalasymptoticdistributionaccessiblealphabetarbitrarybinomial
0
0 comments X
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.