Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.88
URN: urn:nbn:de:0030-drops-34328
URL: https://drops.dagstuhl.de/opus/volltexte/2012/3432/
Bassino, Frédérique ; David, Julien ; Sportiello, Andrea
Asymptotic enumeration of Minimal Automata
| pdf-format: |
|
Abstract
We determine the asymptotic proportion of minimal automata, withinn-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.
BibTeX - Entry
@InProceedings{bassino_et_al:LIPIcs:2012:3432,
author = {Fr{\'e}d{\'e}rique Bassino and Julien David and Andrea Sportiello},
title = {{Asymptotic enumeration of Minimal Automata}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {88--99},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3432},
URN = {urn:nbn:de:0030-drops-34328},
doi = {10.4230/LIPIcs.STACS.2012.88},
annote = {Keywords: minimal automata, regular languages, enumeration of random structures}
}
| Keywords: | minimal automata, regular languages, enumeration of random structures | |
| Seminar: | 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) | |
| Issue date: | 2012 | |
| Date of publication: | 24.02.2012 |
