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
Keywords :
Document type :
Theses
Domain :

Cited literature [41 references]

https://pastel.archives-ouvertes.fr/tel-01136434
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

File

TH2014PEST1111.pdf
Version validated by the jury (STAR)

Identifiers

• HAL Id : tel-01136434, version 1

Citation

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