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

Font Size:  Small  Medium  Large

On the asymptotic enumeration of accessible automata

Elcio Lebensztayn

Abstract


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