Les transducteurs - automates avec sortie - et les relations rationnelles sont des concepts fondamentaux de la théorie des automates. Un rôle particulier est joué par la famille des fonctions rationnelles, en raison de ses propriétés remarquables et aujourd'hui classiques. Les relations de norme bornée sont une généralisation de celles-ci, introduite par Schützenberger en 1976, où le supremum des cardinalités des images est borné par une constante. Ces relations ont reçu une attention particulière en de differents travaux, dont le but a été de généraliser certaines propriétés des fonctions rationnelles; pourtant, les différences entre les techniques mises en oeuvre et la difficulté de quelques preuves conduisent à la nécessité d'une compréhension plus approfondie de ces propriétés. Cette thèse est consacrée à une présentation uniforme de quelques propriétés des relations de norme bornée, centrée sur la représentation de ces relations par des transducteurs et les manipulations de leur structure via des constructions de produits et de revêtements d'automates. Sont traités dans cette approche structurelle la décomposition d'une relation rationnelle de norme bornée dans une somme de fonctions rationnelles, résultat dont il est aussi donné une généralisation, la décidabilité de la famille des relations rationnelles de norme bornée, et la décidabilité de l'équivalence pour ces relations. Les constructions développées dans cette thèse permettent en particulier de nouvelles bornes de complexité, par rapport aux résultats connus.
| Identifer | oai:union.ndltd.org:CCSD/oai:pastel.archives-ouvertes.fr:pastel-00004322 |
| Date | 17 November 2008 |
| Creators | De Souza, Rodrigo |
| Publisher | Télécom ParisTech |
| Source Sets | CCSD theses-EN-ligne, France |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0024 seconds