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.
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 |
Éditer le document (administrateurs uniquement)