Complétude pour les demi-anneaux et algèbres de Kleene étoile-continues avec domaine

Auteur(s): Mbacke, Sokhna Diarra
Direction de recherche: Desharnais, Jules
Résumé: À cause de la complexité croissante des systèmes informatiques, ces derniers sont aujourd’hui étudiés au moyen de multiples modèles et formalismes. Ainsi, il est nécessaire de développer des théories qui unifient différentes approches aafn de limiter les risques d’erreurs lorsqu’on passe d’un formalisme à l’autre. C’est dans cette optique que les monoïdes avec domaine, demi-anneaux avec domaine et algèbres de Kleene avec domaine ont vu le jour, il y a environ une décennie. L’idée est de définir un opérateur de domaine sur des structures algébriques classiques, afin d’unifier l’algèbre et la logique des programmes. La question concernant la complétude pour ces algèbres est encore ouverte. Elle constitue l’objet de ce mémoire. Nous définissons des structures arborescentes appelées arbres avec sommet et représentées sous forme matricielle. Après avoir donné des propriétés fondamentales de ces arbres, nous définissons des relations permettant de les comparer. Ensuite, nous démontrons que, modulo une certaine relation d’équivalence, l’ensemble des arbres avec sommet est muni d’une structure de monoïde avec domaine. Ce résultat permet de définir un modèle pour les demi-anneaux avec domaine et d’en prouver la complétude. Nous définissons également un modèle pour les algèbres de Kleene avec domaine -continues et prouvons la complétude de ce dernier modulo un nouvel axiome.
Type de document: Mémoire de maîtrise
Date de publication: 2018
Date de la mise en libre accès: 14 août 2018
Lien permanent: http://hdl.handle.net/20.500.11794/30666
Université décernant le diplôme: Université Laval
Collection :Thèses et mémoires

Fichier(s) :
Description TailleFormat 
34671.pdf1.14 MBAdobe PDFMiniature
Télécharger
Tous les documents dans CorpusUL sont protégés par la Loi sur le droit d'auteur du Canada.