Global ETD Search

1	Computational aspects of infinite automata simulation and closure system related issues / Aspects de complexité du problème de composition des services web Ennaoui, Karima 28 September 2017 (has links) 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 maximale d’un treillis codé par une relation binaire. Puis, la notion de key-ideal est définie, 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 les key-ideal non minimaux en délai polynomial. / This thesis investigates complexity and computational issues in two parts. The first concerns an issue related to web services composition problem: Deciding whether the behaviour of a web service can be composed out of an existing repository of web services. This question has been reduced to simulating a finite automata to the product closure of an automata set. We study the complexity of this problem considering two parameters; the number of considered instances in the composition and the presence of the so-called hybrid states (states that are both intermediate and final). The second part concerns closure systems and two related issues; Maximal extension of a closure system : we give an incremental polynomial algorithm that computes a lattice's maximal extension when the input is a binary relation. Candidate keys enumeration : we introduce the notion of key-ideal sets and prove that their enumeration is equivalent to candidate keys enumeration. We then give an efficient algorithm that generates all non-minimal key-ideal sets in a polynomial delay and all minimal ones in incremental polynomial time. Service web Comportement de service web Composition de service web Simulation des automates Complexité Exptime-complet Théorie d’ordre Système de fermeture Treillis Extension maximale Bases de données Base d’implications Relation binaire Clé candidate Énumération Délai polynomial Délai incrémental Web service Web service behaviour Web service composition Automata simulation Complexity Product closure of automata Asynchronous product Exptime-complete Order theory Closure system Lattice Maximal extension Database Implicational base Candidate key Binary relation Enumeration Polynomial delay Incremental delay

Search results

Computational aspects of infinite automata simulation and closure system related issues / Aspects de complexité du problème de composition des services web