Completeness for domain semirings and star-continuous Kleene algebras with domain

Authors: Mbacke, Sokhna Diarra
Advisor: Desharnais, Jules
Abstract: 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.
Document Type: Mémoire de maîtrise
Issue Date: 2018
Open Access Date: 20 December 2018
Permalink: http://hdl.handle.net/20.500.11794/33008
Grantor: Université Laval
Collection:Thèses et mémoires

Files in this item:
Description SizeFormat 
x20181.pdf852.13 kBAdobe PDFThumbnail
View/Open
All documents in CorpusUL are protected by Copyright Act of Canada.