Skip to Main content Skip to Navigation

Génération aléatoire d'automates et analyse d'algorithmes de minimisation

Abstract : This thesis is about the uniform random generation of finite automata and the analysisof their state minimization algorithms. Random generators allow to conduct an experimental study on the properties of the generated objectand on the algorithms that apply to this object. It is also a useful tool for research that facilitates the theoretical study of the average behavior of algorithms. Usually, the analysis of an algorithm focuses on the worst case scenario, which is often not representative of thepractical behavior of the algorithm. From a theoretical point of view, one can define what happens "often" by fixing a probability law on the algorithm's inputs. The average analysis consists in the estimation ofthe requested resources, according to this probability distribution.In this context, I worked on several algorithms for the random generation of deterministic accessibleautomata (complete or not).Those algorithms are based on bijective combinatorics, that allows to use generic tools called the Boltzmann generators. I implemented those methods in two softwares : REGAL and PREGA. I studied the average complexity of state minimization algorithms and obtained results showing that theaverage case of the two algorithms due to Moore and Hopcroft is way better than the worst case
Document type :
Complete list of metadata
Contributor : Abes Star :  Contact
Submitted on : Thursday, April 21, 2011 - 9:04:06 AM
Last modification on : Wednesday, February 3, 2021 - 7:54:27 AM
Long-term archiving on: : Thursday, November 8, 2012 - 5:01:00 PM


Version validated by the jury (STAR)


  • HAL Id : tel-00587637, version 1


Julien David. Génération aléatoire d'automates et analyse d'algorithmes de minimisation. Automatique. Université Paris-Est, 2010. Français. ⟨NNT : 2010PEST1016⟩. ⟨tel-00587637⟩