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

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.