Completeness for domain semirings and star-continuous Kleene algebras with domain
|Authors:||Mbacke, Sokhna Diarra|
|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|
|Open Access Date:||20 December 2018|
|Collection:||Thèses et mémoires|
All documents in CorpusUL are protected by Copyright Act of Canada.