Constellation, le dépôt institutionnel de l'Université du Québec à Chicoutimi

Algorithme de calcul du manoïde dérivé d'une boucle finie

Lavoie Éric. (2006). Algorithme de calcul du manoïde dérivé d'une boucle finie. Mémoire de maîtrise, Université du Québec à Chicoutimi.

[thumbnail of 24968251.pdf]
Prévisualisation
PDF
5MB

Résumé

Notre recherche se situe dans le cadre de la théorie algébrique des langages. Il est bien connu que les semigroupes finis peuvent être vus comme des automates finis. Ainsi, ils permettent de reconnaître exactement les langages réguliers. D'une façon similaire, les groupoïdes finis sont associés aux automates à pile et aux langages hors-contextes.

Il a été démontré qu'un type particulier de groupoïdes, les boucles finies, ne reconnaissent que des langages réguliers. Mais les groupoïdes et les boucles sont des structures algébriques non associatives, ce qui rend leur étude très complexe. Cependant, il a été démontré que l'on peut associer à chaque boucle finie un unique monoïde fini nommé le monoïde dérivé de la boucle. Ce monoïde préserve plusieurs propriétés de la boucle. En particulier, il reconnaît l'ensemble des langages reconnus par la boucle concernée, ce qui permet d'utiliser la richesse et l'élégance de la théorie des semigroupes dans l'étude des boucles finies.

Dans ce travail, nous démontrerons que le monoïde dérivé d'une boucle finie est calculable. Par la suite, nous présenterons différentes versions d'un algorithme ayant pour objectif de construire le monoïde dérivé d'une boucle finie. Finalement, nous exposerons et analyserons brièvement quelques résultats calculés sur les boucles d'ordre 8 et moins à l'aide de ces différentes versions de l'algorithme.

Type de document:Thèse ou mémoire de l'UQAC (Mémoire de maîtrise)
Date:2006
Lieu de publication:Chicoutimi
Programme d'étude:Maîtrise en informatique
Nombre de pages:114
ISBN:9781412314022
Identifiant unique:10.1522/24968251
Sujets:Sciences naturelles et génie > Sciences mathématiques > Informatique
Département, module, service et unité de recherche:Départements et modules > Département d'informatique et de mathématique > Programmes d'études de cycles supérieurs en informatique
Directeur(s), Co-directeur(s) et responsable(s):Lemieux, François
Mots-clés:Mathématiques, Algèbre, Monoïdes, THESE, MONOIDE, ALGEBRE, MATHEMATIQUE, SEMIGROUPE, SEMI-GROUPE, THEORIE, ALGEBRIQUE, LANGAGE, ALGORITHME, BOUCLE, FINI, CALCUL
Déposé le:01 janv. 2006 12:34
Dernière modification:20 sept. 2011 15:35
Afficher les statistiques de telechargements

Éditer le document (administrateurs uniquement)

Creative Commons LicenseSauf indication contraire, les documents archivés dans Constellation sont rendus disponibles selon les termes de la licence Creative Commons "Paternité, pas d'utilisation commerciale, pas de modification" 2.5 Canada.

Bibliothèque Paul-Émile-Boulet, UQAC
555, boulevard de l'Université
Chicoutimi (Québec)  CANADA G7H 2B1
418 545-5011, poste 5630