Langages apériodiques et langages complètement réductibles

Kpeglo, Yeena Komi (2014). « Langages apériodiques et langages complètement réductibles » Mémoire. Montréal (Québec, Canada), Université du Québec à Montréal, Maîtrise en mathématiques.

Fichier(s) associé(s) à ce document :
[img]
Prévisualisation
PDF
Télécharger (1MB)

Résumé

Nous caractérisons dans ce travail les langages reconnaissables sans-étoile et les langages reconnaissables complètement réductibles. Les langages sans-étoile sont ceux construits à partir des lettres et en n'utilisant que les opérateurs booléens et produit, mais sans utiliser l'étoile de Kleene. Le principal outil de caractérisation de ces langages, qui utilise le monoïde syntaxique, est le théorème de Schützenberger dont la preuve complète sera exposée. Les langages complètement réductibles sont quant à eux, ceux dont la représentation syntaxique de leur série caractéristique est complètement réductible. Cette famille contient des langages remarquables, tels que les langages birécurrents, en particulier les sous-monoïdes engendrés par un code bifixe.

Type: Mémoire accepté
Informations complémentaires: Le mémoire a été numérisé tel que transmis par l'auteur.
Directeur de thèse: Reutenauer, Christophe
Mots-clés ou Sujets: Langages reconnaissables sans-étoile, Langages reconnaissables complètement réductibles, Théorème de Schützenberger
Unité d'appartenance: Faculté des sciences > Département de mathématiques
Déposé par: Service des bibliothèques
Date de dépôt: 18 juin 2015 12:43
Dernière modification: 18 juin 2015 12:43
Adresse URL : http://archipel.uqam.ca/id/eprint/7043

Statistiques

Voir les statistiques sur cinq ans...