Etude structurelle des transducteurs de norme bornée
Institution:
Paris, ENSTDisciplines:
Directors:
Abstract EN:
Transducers - automata with output - and rational relations are fundamental concepts in the field of automata theory. In particular, the rational functions are an important and well known family of relations due to the remarkable properties they possess. The bounded valued relations are a generalisation of the rational functions introduced by Schützenberger in 1976, where every image has a bounded number of elements. Even though some properties of the rational functions have been shown to hold in this more general setting, the use of techniques of distinct nature and the difficulty of some proofs indicate the need for a deeper understanding of these relations. This thesis brings a uniform presentation of some properties of the bounded valued rational relations, based on the representation by transducers and the manipulation of their structure with the use of produts and coverings of automata. Under this structural approach, it is tackled the decomposition of a bounded valued rational relation into a sum of rational functions and a generalisation, the decidability of the bounded valuedness and of the equivalence for the bounded valued transducers. The constructions developed in this thesis allow in particular clear algorithms with gains of complexity with respect to the known results.
Abstract FR:
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.