Skip to Main content Skip to Navigation
Conference papers

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 metadata

Cited literature [43 references]  Display  Hide  Download
Contributor : Admin Upem Connect in order to contact the contributor
Submitted on : Friday, April 20, 2018 - 4:10:29 PM
Last modification on : Saturday, January 15, 2022 - 3:57:58 AM
Long-term archiving on: : Tuesday, September 18, 2018 - 9:40:00 PM


Files produced by the author(s)




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



Record views


Files downloads