Due to their increasing complexity, today’s computer systems are studied using multiple models and formalisms. Thus, it is necessary to develop theories that unify different approaches in order to limit the risks of errors when moving from one formalism to another. It is in this context that monoids, semirings and Kleene algebras with domain were born about a decade ago. The idea is to define a domain operator on classical algebraic structures, in order to unify algebra and the classical logics of programs. The question of completeness for these algebras is still open. It constitutes the object of this thesis. We define tree structures called trees with a top and represented in matrix form. After having given fundamental properties of these trees, we define relations that make it possible to compare them. Then, we show that, modulo a certain equivalence relation, the set of trees with a top is provided with a monoid with domain structure. This result makes it possible to define a model for semirings with domain and prove its completeness. We also define a model for -continuous Kleene algebras with domain as well and prove its completeness modulo a new axiom.
| Identifer | oai:union.ndltd.org:LAVAL/oai:corpus.ulaval.ca:20.500.11794/33008 |
| Date | 20 December 2018 |
| Creators | Mbacke, Sokhna Diarra |
| Contributors | Desharnais, Jules |
| Source Sets | Université Laval |
| Language | English |
| Detected Language | English |
| Type | mémoire de maîtrise, COAR1_1::Texte::Thèse::Mémoire de maîtrise |
| Format | 1 ressource en ligne (iv, 131 pages), application/pdf |
| Rights | http://purl.org/coar/access_right/c_abf2 |
| Relation | http://hdl.handle.net/20.500.11794/30666 |
Page generated in 0.0024 seconds