Nos tutelles

CNRS

Nos partenaires


Accueil > Publications > Thèses

ENNAOUI Karima


Computational aspects of infinite automata simulation and closure systems related issues

Jeudi 28 septembre 2017 - 14 h 00 - Amphi Bruno Garcia, Bâtiment E - ISIMA

La thèse est consacrée à des problématiques d’algorithmique et de complexité sur deux sujets. Le premier sujet s’intéresse à la composition comportementale des services web. Ce problème a été réduit à la simulation d’un automate par le produit fermé d’un ensemble d’automates. La thèse étudie dans sa première partie la complexité de ce problème en considérant deux paramètres : le nombre des instances considéré de chaque service et la présence des états hybrides : état à la fois intermédiaire et final dans un automate. Le second sujet porte sur les systèmes de fermeture et s’intéresse au calcul de l’extension maximale d’un système de fermeture ainsi qu’à l’énumération des clefs candidates d’une base implicative. On donne un algorithme Incrémental Polynomial qui génère l’extension maximal d’un treillis codé par une relation binaire. Puis, la notion de key-ideal est défini, en prouvant que leur énumération est équivalente à l’énumération des clefs candidates. Ensuite, on donne un algorithme qui permet de générer les key-ideal minimaux en temps Incrémental Polynomial et ensuite les key-ideal non minimaux en délai polynomial.

Membres de Jury :

Prof. Arnaud Durand - Université Denis Diderot - Paris 7, Rapporteur et Examinateur
Prof. Marianne Huchard - Université de Montpellier, Rapporteur et Examinateur
Dr. Karell Bertet - Université de La Rochelle, Examinateur
Prof. Jean-Marc Petit - LIRIS Lyon, Examinateur
Dr. Arnaud Mary - LBBE Lyon, Invité
Prof. Lhouari Nourine - Université Clermont Auvergne, Directeur de thèse
Prof. Farouk Toumani - Université Clermont Auvergne, Co-encadrant de thèse.