2026-07-23T20:44:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3432 2024-03-06T10:34:09Z ddc:004 open_access

Asymptotic enumeration of Minimal Automata Bassino, Frédérique David, Julien Sportiello, Andrea minimal automata regular languages enumeration of random structures 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Frédérique Bassino and Julien David and Andrea Sportiello 2012 Is Part Of LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2012.88 urn:nbn:de:0030-drops-34328 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.88 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode