Asymptotic enumeration of Minimal Automata

2011/09/26 by Frédérique Bassino, Frederique Bassino, Bassino, Frederique +4 · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Cellular Automata and Applications #Combinatorics (math.CO) #F.2 #FOS: Computer and information sciences #FOS: Mathematics #Formal Languages and Automata Theory (cs.FL) #cs.FL #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1109.5683

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

arxiv created 2011/09/26 · openalex publication_date 2011/09/26 · arxiv updated 2011/09/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Minimality of Random Moore Automata under Prefix-Dependent Congruences

Related

• On the Average Complexity of Moore's State Minimization Algorithm
• Slowly synchronizing automata with zero and incomplete sets
• A Congruence-based Perspective on Automata Minimization Algorithms
• Bounds on the Automata Size for Presburger Arithmetic
• Aspects of enumeration and generation with a string automata representation