Asymptotic enumeration of Minimal Automata

Details Asymptotic enumeration of Minimal Automata Asymptotic enumeration of Minimal Automata

2011-09-26

arxiv.org/abs/1109.5683v1

Computer Science

Formal Languages and Automata Theory

12+5 pages, 2 figures, submitted to STACS 2012

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Asymptotic enumeration of Minimal Automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Asymptotic enumeration of Minimal Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotic enumeration of Minimal Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-690214