Asymptotic enumeration of minimal automata

DOI10.4230/LIPICS.STACS.2012.88zbMATH Open1245.68118arXiv1109.5683MaRDI QIDQ2904752FDOQ2904752

Authors: Frédérique Bassino, Julien David, Andrea Sportiello 

Publication date: 23 August 2012

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.

Full work available at URL: https://arxiv.org/abs/1109.5683

Recommendations

• On the asymptotic enumeration of accessible automata
• Distribution of the number of accessible states in a random deterministic automaton
• Exact enumeration of acyclic deterministic automata
• Enumeration and random generation of accessible automata
• Random deterministic automata

zbMATH Keywords

minimal automataregular languagesenumeration of random structures

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Cited In (12)

• On the asymptotic enumeration of accessible automata
• Sturmian and Infinitely Desubstitutable Words Accepted by an $$\omega $$-Automaton
• Compacted binary trees admit a stretched exponential
• Enumeration of minimal acyclic automata via generalized parking functions
• The minimal automaton recognizing \(m\mathbb N\) in a linear numeration system
• The state complexity of random DFAs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Counting Minimal Symmetric Difference NFAs
• Enumerating regular expressions and their languages
• Asymptotics of Minimal Deterministic Finite Automata Recognizing a Finite Binary Language
• Random deterministic automata

This page was built for publication: Asymptotic enumeration of minimal automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904752)