• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 1
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Etude topologique de fonctions définissables par automates

Benoit, Cagnard 28 November 2008 (has links) (PDF)
L'objet de cette thèse est l'étude de la complexité topologique de fonctions omega-rationnelles : fonctions de mots infinis dont le graphe est reconnaissable par automate fini. Le cadre de notre étude est celui de la hiérarchie des boréliens et des classes de Baire. On remarque tout d'abord que ces fonctions sont au plus de classe 2. Christophe Prieur a montré que le problème de la continuité est décidable. Nous avons montré qu'être de classe 1 est aussi décidable dans le cas synchrone en adaptant un résultat de Sierpinski portant sur les sur et sous-graphes à notre contexte. Notre attention s'est ensuite portée aux points de continuité de telles fonctions. Un résultat de Baire dit qu'une fonction n'est pas de classe 1 si et seulement si il existe un fermé non vide sur lequel la fonction n'admet aucun point de continuité. Nous prouvons une version automate de ce théorème : Une fonction omega-rationnelle n'est pas de classe 1 si et seulement si il existe un fermé non vide reconnaissable par un automate de Büchi tel que la restriction de la fonction à ce fermé n'ait aucun point de continuité. Ce résultat est prouvé en utilisant la dérivation de Hausdorff qui s'arrête au bout d'un nombre fini d'étapes sur les langages omega-rationnels Ce travail s'est conclu par l'étude des orbites des fonctions réelles définissables en base Pisot par des transducteurs synchrones. L'ordre de Sarkovski permet de classifier les ordres des orbites périodiques des fonction réelles continues. Le résultat principal obtenu est la décidabilité pour tout entier n de l'existence d'orbites périodiques de cardinalité n et par suite de toute cardinalité inférieure dans l'ordre de Sarkovski.

Page generated in 0.0666 seconds