Random Deterministic Automata

Cyril Nicaud (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

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.

Domaines: Théorie et langage formel [cs.FL]

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