Les travaux développés dans cette thèse empruntent trois directions principales. D'une part, une étude attentive des propriétés de l'automate universel d'un langage rationnel a été menée. Cet automate fini (introduit sous une forme sensiblement différente par J.H. Conway) accepte le langage et a la particularité de contenir l'image par morphisme de n'importe quel automate équivalent. Nous donnons un algorithme pour le construire à partir de l'automate minimal. L'exploitation des propriétés de l'automate universel d'un langage réversible nous a permis de montrer qu'il existe un sous-automate quasi-réversible (à partir duquel on peut facilement construire un automate réversible) de l'automate universel équivalent. De plus, il existe un tel sous-automate sur lequel on peut calculer une expression rationnelle qui représente le langageavec une hauteur d'étoile minimale. D'autre part, nous donnons un algorithme pour décider la séquentialité d'une série (max,+) ou (min,+) réalisée par par un automate sur un alphabet à une lettre. La complexité de cet algorithme ne dépend que de la structure de l'automate et non des valeurs des coefficients. Nous présentons aussi un algorithme qui permet de procéder directement à la déterminisation d'un automate réalisant une série séquentielle et, si ce n'est pas le cas, à l'obtention d'un automate équivalent non ambigu. Ce dernier point rejoint le résultat de Stéphane Gaubert qui montre qu'on peut obtenir une expression (et donc un automate) non ambiguë pour n'importe quel série (max,+) rationnelle sur une lettre. Enfin, nous proposons un algorithme pour construire, à partir d'une expression rationnelle avec multiplicité, un automate qui représente la même série. Cet algorithme, qui est la généralisation des travaux d'Antimirov, permet d'obtenir explicitement un ensemble fini d'expressions qui représentent un ensemble générateur du semi-module auquel appartiennent les quotients de la série rationnelle.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00737830 |
| Date | 19 December 2001 |
| Creators | Lombardy, Sylvain |
| Publisher | Ecole nationale supérieure des telecommunications - ENST |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0559 seconds