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 :
Theses
Complete list of metadatas

https://pastel.archives-ouvertes.fr/tel-00587637
Contributor : Abes Star <>
Submitted on : Thursday, April 21, 2011 - 9:04:06 AM
Last modification on : Thursday, January 10, 2019 - 2:47:13 PM
Long-term archiving on : Thursday, November 8, 2012 - 5:01:00 PM

File

TH2010PEST1016.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : tel-00587637, version 1

Citation

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⟩

Share

Metrics

Record views

664

Files downloads

181