Global ETD Search

1	The Complexity of Finite Model Reasoning in Description Logics Lutz, Carsten, Sattler, Ulrike, Tendera, Lidia 30 May 2022 (has links) We analyze the complexity of finite model reasoning in the description logic ALCQI, i.e. ALC augmented with qualifying number restrictions, inverse roles, and general TBoxes. It turns out that all relevant reasoning tasks such as concept satisfiability and ABox consistency are EXPTIME-complete, regardless of whether the numbers in number restrictions are coded unarily or binarily. Thus, finite model reasoning with ALCQI is not harder than standard reasoning with ALCQI. info:eu-repo/classification/ddc/004 ddc:004
2	PDL with Negation of Atomic Programs Lutz, Carsten, Walther, Dirk 30 May 2022 (has links) Propositional dynamic logic (PDL) is one of the most succesful variants of modal logic. To make it even more useful for applications, many extensions of PDL have been considered in the literature. A very natural and useful such extension is with negation of programs. Unfortunately, it is long-known that reasoning with the resulting logic is undecidable. In this paper, we consider the extension of PDL with negation of atomic programs, only. We argue that this logic is still useful, e.g. in the context of description logics, and prove that satisfiability is decidable and EXPTIME-complete using an approach based on Büchi tree automata. info:eu-repo/classification/ddc/004 ddc:004
3	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

1

Page generated in 0.0376 seconds