Discrete Mathematics & Theoretical Computer Science, Vol 12, No 3 (2010)

Font Size:  Small  Medium  Large

On the asymptotic enumeration of accessible automata

Elcio Lebensztayn


We simplify the known formula for the asymptotic estimate of the number of deterministic and accessible automata with n states over a k-letter alphabet. The proof relies on the theory of Lagrange inversion applied in the context of generalized binomial series.

Full Text: PDF PostScript