[Zurück]

M. Wallner, A. Price, W. Fang:
"Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language";
Vortrag: AofA 2020, Klagenfurt; 15.06.2020 - 20.06.2020; in: "31st International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2020)", M. Drmota, C. Heuberger (Hrg.); Leibniz International Proceedings in Informatics (LIPIcs), 159 (2020), ISBN: 978-3-95977-147-4; S. 1 - 13.

We show that the number of minimal deterministic finite automata with n+1 states recognizing a finite binary language grows asymptotically for n → ∞ like Θ(n! 8ⁿ e^{3 a₁ n^{1/3}} n^{7/8}), where a₁ ≈ -2.338 is the largest root of the Airy function. For this purpose, we use a new asymptotic enumeration method proposed by the same authors in a recent preprint (2019). We first derive a new two-parameter recurrence relation for the number of such automata up to a given size. Using this result, we prove by induction tight bounds that are sufficiently accurate for large n to determine the asymptotic form using adapted Netwon polygons.

http://dx.doi.org/10.4230/LIPIcs.AofA.2020.11