Automates codéterministes et automates acycliques : analyse d'algorithmes et génération aléatoire

Abstract : The general context of this thesis is the quantitative analysis of objects coming from rational language theory. We adapt techniques from the field of analysis of algorithms (average-case complexity, generic complexity, random generation...) to objects and algorithms that involve particular classes of automata. In a first part we study the complexity of Brzozowski's minimisation algorithm. Although the worst-case complexity of this algorithm is bad, it is known to be efficient in practice. Using typical properties of random mappings and random permutations, we show that the generic complexityof Brzozowski's algorithm grows faster than any polynomial in n, where n is the number of states of the automaton. In a second part, we study the random generation of acyclic automata. These automata recognize the finite sets of words, and for this reason they are widely use in applications, especially in natural language processing. We present two random generators, one using a model of Markov chain, the other a ``recursive method", based on a cominatorics decomposition of structures. The first method can be applied in many situations cases but is very difficult to calibrate, the second method is more efficient. Once implemented, this second method allows to observe typical properties of acyclic automata of large size
Document type :
Complete list of metadatas

Cited literature [41 references]  Display  Hide  Download
Contributor : Abes Star <>
Submitted on : Friday, March 27, 2015 - 11:32:34 AM
Last modification on : Thursday, July 5, 2018 - 2:46:11 PM
Long-term archiving on : Tuesday, April 18, 2017 - 1:32:32 AM


Version validated by the jury (STAR)


  • HAL Id : tel-01136434, version 1


Sven de Félice. Automates codéterministes et automates acycliques : analyse d'algorithmes et génération aléatoire. Informatique. Université Paris-Est, 2014. Français. ⟨NNT : 2014PEST1111⟩. ⟨tel-01136434⟩



Record views


Files downloads