Dans ce travail, nous nous intéressons aux séries rationnelles et aux matrices génériques non commutatives.
Dans le premier chapitre, on étudiera les polynômes de cliques du graphe pondéré. Soit C un graphe simple non orienté (sans boucles), on lui associe la somme des monômes (-1)i CiXi où Ci est le nombre de sous-graphes complets (cliques) sur i sommets. En pondérant les sommets par des entiers non négatifs, on définit les polynômes de cliques du graphe pondéré C comme étant la somme des monômes (-1)|B|xdeg(B), où B est un sous-graphe complet de C. On va montrer que l'ensemble de tels polynômes coïncide avec l'ensemble des polynômes réciproques des polynômes caractéristiques de matrices à coefficients entiers non négatifs. Au chapitre 2, on va généraliser ce polynôme une fois de plus en pondérant les sommets du graphe simple par des monômes de la forme αxd , où α est un réel positif et d, un entier non négatif. On va lui associer le polynôme de cliques généralisé comme la somme (-1)IBI (∏sЄB αsxds ), où B est un sous-ensemble commutatif de C et s est un sommet de B. On va montrer que l'ensemble de ces polynômes coïncide exactement avec l'ensemble des polynômes réciproques des polynômes caractéristiques à coefficients réels non négatifs. Le troisième chapitre porte sur la N-rationalité de certaines classes de séries. Tout d'abord, on va établir les conditions nécessaires et suffisantes nous permettant de décider de la N-rationalité d'une série de la forme (1-ax +bxk)-1, où a Є N, b Є Z, k ≥ 2 . Par la suite, on fera de même pour les séries de la forme (1-ax + bx2 + cx3)-1, où a Є N et b, c Є Z. Au Chapitre 4, on étudiera les propriétés des fonctions zêta associées aux automates et aux codes. On va montrer que le nombre de chemins bi-infinis dans A dont la période est n est égal au rang stable d'un certain mot non vide w; i.e. le rang de wn pour un n suffisamment grand. Par ailleurs, on montrera plusieurs propriétés de cette série telles la N-rationalité, l'apériodicité ou la divergence. Étant donné que plusieurs de ces résultats sont valides pour des automates non ambigus, ceux-ci s'appliqueront aux codes. On y présentera les propriétés de la fonction zêta des codes complets, des codes purs, des codes circulaires et des codes bifixes. Le chapitre 5 portera sur les matrices génériques stochastiques, i.e. les matrices à variables non commutatives soumises aux conditions stochastiques (somme des éléments de chaque ligne vaut 1). Il est bien connu dans la littérature que toute matrice stochastique
a 1 comme valeur propre dont le vecteur propre à droite associé est t (1, ... , 1). Mais qu'en est-il du vecteur propre à gauche associé à cette même valeur propre? Dans le cas commutatif, on montrera que ce vecteur de la matrice M est le vecteur ligne des mineurs principaux M - In. Dans le cas non-commutatif, on montrera que les éléments de ce vecteur sont les inverses des dérivations des codes reconnus par l'automate dont M est la matrice associée, évalués dans un corps libre. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Séries rationnelles, Codes à longueurs variables, Fonction zêta, Automate, Corps libre, Matrices génériques, Polynômes de cliques.
Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMUQ.2356 |
Date | January 2009 |
Creators | Lavallée, Sylvain |
Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
Detected Language | French |
Type | Thèse acceptée, NonPeerReviewed |
Format | application/pdf |
Relation | http://www.archipel.uqam.ca/2356/ |
Page generated in 0.0017 seconds