Random Deterministic Automata

Abstract : In this article, we consider deterministic automata under the paradigm of average case analysis of algorithms. We present the main results obtained in the literature using this point of view, from the very beginning with Korshunov's theorem about the asymptotic number of accessible automata to the most recent advances, such as the average running time of Moore's state minimization algorithm or the estimation of the probability that an automaton is minimal. While focusing on results, we also try to give an idea of the main tools used in this field.
Document type :
Conference papers
Complete list of metadatas

Cited literature [43 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01772890
Contributor : Admin Upem <>
Submitted on : Friday, April 20, 2018 - 4:10:29 PM
Last modification on : Thursday, July 5, 2018 - 2:46:10 PM
Long-term archiving on : Tuesday, September 18, 2018 - 9:40:00 PM

File

mfcs14.pdf
Files produced by the author(s)

Identifiers

Citation

Cyril Nicaud. Random Deterministic Automata. MFCS 2014, Aug 2014, Budapest, Hungary. pp.5-23, ⟨10.1007/978-3-662-44522-8_2⟩. ⟨hal-01772890⟩

Share

Metrics

Record views

141

Files downloads

96