Dans la première partie de ce manuscrit nous étudions les fonctions rationnelles, c'est-à-dire définies par des transducteurs unidirectionnels. Notre objectif est d'étendre aux transductions les nombreuses correspondances logique-algèbre qui ont été établies concernant les langages, notamment le célèbre théorème de Schützenberger-McNaughton-Papert. Dans le cadre des fonctions rationnelles sur les mots finis, nous obtenons une caractérisation à la Myhill-Nerode en termes de congruences d'indice fini. Cette caractérisation nous permet d'obtenir un résultat de transfert, à partir d'équivalences logique-algèbre pour les langages vers des équivalences pour les transductions. En particulier nous montrons comment décider si une fonction rationnelle est définissable en logique du premier ordre. Sur les mots infinis, nous pouvons également décider la définissabilité en logique du premier ordre, mais avec des résultats moins généraux.Dans la seconde partie nous introduisons une logique pour les transductions et nous résolvons le problème de synthèse régulière : étant donnée une formule de la logique, peut-on obtenir un transducteur bidirectionnel déterministe satisfaisant la formule ? Les fonctions réalisées par des transducteurs bidirectionnels déterministes sont caractérisés par plusieurs modèles différents, y compris par les transducteurs MSO, et ont ainsi été nommées transductions régulières. Plus précisément nous fournissons un algorithme qui produit toujours une fonction régulière satisfaisant une spécification donnée en entrée.Nous exposons également un lien intéressant entre les transductions et les mots avec données. Par conséquent nous obtenons une logique expressive pour les mots avec données, pour laquelle le problème de satisfiabilité est décidable. / In the first part of this manuscript we focus on the study of rational functions, functions defined by one-way transducers.Our goal is to extend to transductions the many logic-algebra correspondences that have been established for languages, such as the celebrated Schützenberger-McNaughton-Papert Theorem. In the case of rational functions over finite words, we obtain a Myhill-Nerode-like characterization in terms of congruences of finite index. This characterization allows us to obtain a transfer result from logic-algebra equivalences for languages to logic-algebra equivalences for transductions. In particular, we show that one can decide if a rational function can be defined in first-order logic.Over infinite words, we obtain weaker results but are still able to decide first-order definability.In the second part we introduce a logic for transductions and solve the regular synthesis problem: given a formula in the logic, can we obtain a two-way deterministic transducer satisfying the formula?More precisely, we give an algorithm that always produces a regular function satisfying a given specification.We also exhibit an interesting link between transductions and words with ordered data. Thus we obtain as a side result an expressive logic for data words with decidable satisfiability.
| Identifer | oai:union.ndltd.org:theses.fr/2018BORD0185 |
| Date | 12 October 2018 |
| Creators | Lhote, Nathan |
| Contributors | Bordeaux, Université libre de Bruxelles (1970-....), Gauwin, Olivier, Filiot, Emmanuel |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.0023 seconds