• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 2
  • Tagged with
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 2
  • 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

Langages reconnaissables de mots indexés par des ordinaux

Bedon, Nicolas 15 January 1998 (has links) (PDF)
Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux. Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur , celle pour les mots de longueur inférieure à , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable. Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur aux mots de longueur inférieure à , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les -semigroupes et les -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable. Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.
2

Langages reconnaissables de mots indexés par des ordinaux

Bedon, Nicolas 15 January 1998 (has links) (PDF)
Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux.<br /><br />Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur [$\omega$] , celle pour les mots de longueur inférieure à [$\omega^(n+1)$] , où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable.<br /><br />Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur [$\omega$] , qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur [$\omega$] aux mots de longueur inférieure à [$\omega^(n+1)$] , puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les [$\omega^n$] -semigroupes et les [$\omega_1$] -semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à [$\omega^(n+1)$] et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur [$\omega$] , une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les [$\omega_1$] -semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable.<br /><br />Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à [$\omega^(n+1)$] , et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.

Page generated in 0.083 seconds