61 |
Least common subsumers, most specific concepts, and role-value-maps in a description logic with existential restrictions and terminological cyclesBaader, Franz 30 May 2022 (has links)
In a previous report we have investigates subsumption in the presence of terminological cycles for the description logic EL, which allows conjunctions, existential restrictions, and the top concept, and have shown that the subsumption problem remains polynomial for all three types of semantics usually considered for cyclic definitions in description logics. This result depends on a characterization of subsumption through the existence of certain simulation relations on the graph associated with a terminology. In the present report we will use this characterization to show how the most specific concept and the least common subsumer can be computed in EL with cyclic definitions. In addition, we show that subsumption in EL (with or without cyclic definitions) remains polynomial even if one adds a certain restricted form of global role-value-maps to EL. In particular, this kind of role-value-maps can express transitivity of roles.
|
62 |
Role-Value Maps and General Concept Inclusions in the Description Logic FL₀Baader, Franz, Théron, Clément 20 June 2022 (has links)
We investigate the impact that general concept inclusions and role-value maps have on the complexity and decidability of reasoning in the Description Logic FL₀. On the one hand, we give a more direct proof for ExpTimehardness of subsumption w.r.t. general concept inclusions in FL₀. On the other hand, we determine restrictions on role-value maps that ensure decidability of subsumption, but we also show undecidability for the cases where these restrictions are not satisfied.
|
63 |
Deductive Module Extraction for Expressive Description Logics: Extended VersionKoopmann, Patrick, Chen, Jieying 20 June 2022 (has links)
In deductive module extraction, we determine a small subset of an ontology for a given vocabulary that preserves all logical entailments that can be expressed in that vocabulary. While in the literature stronger module notions have been discussed, we argue that for applications in ontology analysis and ontology reuse, deductive modules, which are decidable and potentially smaller, are often sufficient. We present methods based on uniform interpolation for extracting different variants of deductive modules, satisfying properties such as completeness, minimality and robustness under replacements, the latter being particularly relevant for ontology reuse. An evaluation of our implementation shows that the modules computed by our method are often significantly smaller than those computed by existing methods. / This is an extended version of the article in the proceedings of IJCAI 2020.
|
64 |
Computing Compliant Anonymisations of Quantified ABoxes w.r.t. EL Policies: Extended VersionBaader, Franz, Kriegel, Francesco, Nuradiansyah, Adrian, Peñaloza, Rafael 20 June 2022 (has links)
We adapt existing approaches for privacy-preserving publishing of linked data to a setting where the data are given as Description Logic (DL) ABoxes with possibly anonymised (formally: existentially quantified) individuals and the privacy policies are expressed using sets of concepts of the DL EL. We provide a chacterization of compliance of such ABoxes w.r.t. EL policies, and show how optimal compliant anonymisations of ABoxes that are noncompliant can be computed. This work extends previous work on privacypreserving ontology publishing, in which a very restricted form of ABoxes, called instance stores, had been considered, but restricts the attention to compliance. The approach developed here can easily be adapted to the problem of computing optimal repairs of quantified ABoxes. / This is an extended version of an article pulished in: Proceedings of the 19th International Semantic Web Conference (ISWC 2020), Springer LNCS
|
65 |
Computing Safe Anonymisations of Quantified ABoxes w.r.t. EL Policies: Extended VersionBaader, Franz, Kriegel, Francesco, Nuradiansyah, Adrian, Peñaloza, Rafael 20 June 2022 (has links)
In recent work, we have shown how to compute compliant anonymizations of quantified ABoxes w.r.t. EL policies. In this setting, quantified ABoxes can be used to publish information about individuals, some of which are anonymized. The policy is given by concepts of the Description Logic (DL) EL, and compliance means that one cannot derive from the ABox that some non-anonymized individual is an instance of a policy concept. If one assumes that a possible attacker could have additional knowledge about some of the involved non-anonymized individuals, then compliance with a policy is not sufficient. One wants to ensure that the quantified ABox is safe in the sense that none of the secret instance information is revealed, even if the attacker has additional compliant knowledge. In the present paper, we show that safety can be decided in polynomial time, and that the unique optimal safe anonymization of a non-safe quantified ABox can be computed in exponential time, provided that the policy consists of a single EL concept. / This is an extended version of an article published in: Proceedings of the 36th ACM/SIGAPP Symposium on Applied Computing (SAC ’21), ACM
|
66 |
Making Quantification Relevant Again —the Case of Defeasible EL⊥Pensel, Maximilian, Turhan, Anni-Yasmin 20 June 2022 (has links)
Defeasible Description Logics (DDLs) extend Description Logics with defeasible concept inclusions. Reasoning in DDLs often employs rational or relevant closure according to the (propositional) KLM postulates. If in DDLs with quantification a defeasible subsumption relationship holds between concepts, this relationship might also hold if these concepts appear in existential restrictions. Such nested defeasible subsumption relationships were not detected by earlier reasoning algorithms—neither for rational nor relevant closure. In this report, we present a new approach for EL ⊥ that alleviates this problem for relevant closure (the strongest form of preferential reasoning currently investigated) by the use of typicality models that extend classical canonical models by domain elements that individually satisfy any amount of consistent defeasible knowledge. We also show that a certain restriction on the domain of the typicality models in this approach yields inference results that correspond to the (weaker) more commonly known rational closure. / Abriged versions appeared in the proceedings of DARe and LPNMR 2017
|
67 |
Repairing Description Logic Ontologies by Weakening AxiomsBaader, Franz, Kriegel, Francesco, Nuradiansyah, Adrian, Peñaloza, Rafael 20 June 2022 (has links)
The classical approach for repairing a Description Logic ontology O in the sense of removing an unwanted consequence α is to delete a minimal number of axioms from O such that the resulting ontology O´ does not have the consequence α. However, the complete deletion of axioms may be too rough, in the sense that it may also remove consequences that are actually wanted. To alleviate this problem, we propose a more gentle way of repair in which axioms are not necessarily deleted, but only weakened. On the one hand, we investigate general properties of this gentle repair method. On the other hand, we propose and analyze concrete approaches for weakening axioms expressed in the Description Logic EL.
|
68 |
Ontology-Mediated Query Answering for Probabilistic Temporal Data with EL Ontologies: Extended VersionKoopmann, Patrick 20 June 2022 (has links)
Especially in the field of stream reasoning, there is an increased interest in reasoning about temporal data in order to detect situations of interest or complex events. Ontologies have been proved a useful way to infer missing information from incomplete data, or simply to allow for a higher order vocabulary to be used in the event descriptions. Motivated by this, ontology-based temporal query answering has been proposed as a means for the recognition of situations and complex events. But often, the data to be processed do not only contain temporal information, but also probabilistic information, for example because of uncertain sensor measurements. While there has been a plethora of research on ontologybased temporal query answering, only little is known so far about querying temporal probabilistic data using ontologies. This work addresses this problem by introducing a temporal query language that extends a well-investigated temporal query language with probability operators, and investigating the complexity of answering queries using this query language together with ontologies formulated in the description logic EL.
|
69 |
Subsumption in Finitely Valued Fuzzy ELBorgwardt, Stefan, Cerami, Marco, Peñaloza, Rafael 20 June 2022 (has links)
Aus der Einleitung:
Description Logics (DLs) are a family of knowledge representation formalisms that are successfully applied in many application domains. They provide the logical foundation for the Direct Semantics of the standard web ontology language OWL2. The light-weight DL EL, underlying the OWL2 EL profile, is of particular interest since all common reasoning problems are polynomial in this logic, and it is used in many prominent biomedical ontologies like SNOMEDCT and the Gene Ontology.
|
70 |
Adding Threshold Concepts to the Description Logic ELBaader, Franz, Brewka, Gerhard, Gil, Oliver Fernández 20 June 2022 (has links)
We introduce an extension of the lightweight Description Logic EL that allows us to de_ne concepts in an approximate way. For this purpose, we use a graded membership function, which for each individual and concept yields a number in the interval [0, 1] expressing the degree to which the individual belongs to the concept. Threshold concepts C~t for ~ then collect all the individuals that belong to C with degree ~ t. We generalize a well-known characterization of membership in EL concepts to construct a specific graded membership function deg, and investigate the complexity of reasoning in the Description Logic τEL(deg), which extends EL by threshold concepts defined using deg. We also compare the instance problem for threshold concepts of the form C>t in τEL(deg) with the relaxed instance queries of Ecke et al.
|
Page generated in 0.0646 seconds