Contributions à la théorie et aux applications des automates à multiplicités
Institution:
RouenDisciplines:
Directors:
Abstract EN:
This thesis is a work based on publications in Theoretical Computer Science. It consists of two contributions of the theory of automata with multiplicities. This structure has many applications to connected sciences (Computer Sciences, Mathematics, Physics, …). A particular type of automata with multiplicities is the automaton with ε-transitions denoted by k-ε-automaton. In the first part, we give an algebraic method for removing the ε-transitions of the k-ε-automaton in order to obtain an equivalent k-automaton with the same behaviour. We discuss two aspects of the star problem (by infinite sums and by equations). The theory of minimization allows to minimize a k-automaton in the sense of reducing to the smallest among the number of states. It can be used with some modification to solve other problems such as the splitting of modules. We have used the algorithm of decomposition to split a Boolean function which constitute the non linear element of the cryptographic algorithm and to split a ц-module where ц is the Hecke algebra as q=0.
Abstract FR:
Ce mémoire de thèse est un travail autour de publications en Informatique Théorique. Il contient deux contributions à la théorie des automates à Multiplicités, structure qui s'applique avec succès aux sciences voisines (Informatique, Mathématique, Physique, …). Un type particulier d'automates à multiplicités est constitué des automates avec ε-transitions notés k-ε-automates. Dans la première partie, on donne une méthode algébrique pour éliminer les ε-transitions de ces k-ε-automates afin d'obtenir un k-automate équivalent ayant le même comportement. Nous discutons les deux aspects du problème de l'étoile (par somme infinie et par équations). La théorie de la minimisation permet de minimiser un k-automate, au sens de réduire au maximum son nombre d'états tout en conservant le même comportement. Elle peut être utilisée, avec une légère modification, pour résoudre d'autres problèmes. Deux applications sont développées : dans un premier temps, on a utilisé cet algorithme de décomposition pour casser des fonctions booléennes, qui constituent l'élément non linéaire des algorithmes cryptographiques. La deuxième application consiste à décomposer des ц-modules où ц est l'algèbre de Hecke à q=0.