Rational Series and Length Distributions
Bassino, Frédérique
HAL, tel-00719366 / Harvested from HAL
Ce travail porte sur les séries à coefficients entiers positifs, sur les séries N-rationnelles et est centré autour de deux types de questions : le problème de la hauteur d'étoile et l'étude des propriétés des distributions de longueurs des codes. On étudie le problème de la hauteur d'étoile de séries rationnelles particulières : les séries N-rationnelles en une variable. On caractérise de différentes façons les séries N-rationnelles qui sont de hauteur d'étoile 1, et on donne un critère permettant de décider de la hauteur d'étoile d'une classe importante de séries N-rationnelles en une variable. L'étude de la hauteur d'étoile des séries N-rationnelles en une variable repose sur l'utilisation des propriétés de leurs représentations par des matrices. On établit, en particulier, à partir d'un résultat d'Handelman, une caractérisation du rayon spectral d'une matrice compagnon irréductible à coefficients entiers positifs. On étudie, ensuite, les distributions de longueurs des codes circulaires et des codes préfixes. On prouve trois nouveaux résultats concernant les codes circulaires. On généralise, dans plusieurs directions, la caractérisation des distributions de longueurs des codes circulaires établie dans le cas d'un alphabet fini par Schützenberger. D'une part, on remplace l'alphabet fini par un alphabet quelconque dont les éléments ont des poids, ce qui permet d'étendre le résultat à deux distributions de longueurs. D'autre part, on restreint les conditions, ce qui permet d'établir la décidabilité dans le cas d'une distribution finie. On donne une nouvelle formulation de cette caractérisation. Ce résultat, établi par des méthodes combinatoires, met en évidence la décidabilité dans le cas d'une distribution finie. On établit une condition nécessaire et suffisante pour qu'une suite d'entiers positifs soit la distribution de longueur d'un code circulaire maximal sur un alphabet fini. Enfin, on met en évidence les liens entre les séries génératrices des codes préfixes rationnels et une classe de séries N-rationnelles : les DOL-séries. On donne une condition suffisante pour qu'une suite N-rationnelle soit la distribution de longueurs d'un code rationnel préfixe maximal sur un alphabet à k lettres.
Publié le : 1996-11-22
Classification:  mathematical series,  rational function,  coding,  prefix code,  mathematical matrix,  spectral radius,  série mathématique,  fonction rationnelle,  codage,  code préfixe,  matrice mathématique,  rayon spectral,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]
@article{tel-00719366,
     author = {Bassino, Fr\'ed\'erique},
     title = {Rational Series and Length Distributions},
     journal = {HAL},
     volume = {1996},
     number = {0},
     year = {1996},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/tel-00719366}
}
Bassino, Frédérique. Rational Series and Length Distributions. HAL, Tome 1996 (1996) no. 0, . http://gdmltest.u-ga.fr/item/tel-00719366/