Attribut:Abstract
Aus International Center for Computational Logic
Dies ist eine Eigenschaft des Typs Text.
A
Similarity measures for concepts written in Description Logics (DLs) are often devised based on the syntax of concepts or simply by adjusting them to a set of instance data. These measures do not take the semantics of the concepts into account and can thus lead to unintuitive results. It even remains unclear how these measures behave if applied to new domains or new sets of instance data.
In this paper we develop a framework for similarity measures for ELH-concept descriptions based on the semantics of the DL ELH. We show that our framework ensures that the measures resulting from instantiations fulfill fundamental properties, such as equivalence invariance, yet the framework provides the flexibility to adjust measures to specifics of the modelled domain. +
We introduce the design of a fully parallel framework for quickly analyzing large-scale RDF data over distributed architectures. We present three core operations of this framework: dictionary encoding, parallel joins and indexing processing. Preliminary experimental results on a commodity cluster show that we can load large RDF data very fast while remaining within an interactive range for query processing. +
We present a general form of attribute exploration, a knowledge completion algorithm from formal concept analysis. The aim of this generalization is to extend the applicability of attribute exploration by a general description. Additionally, this may also allow for viewing different existing variants of attribute exploration as instances of a general form, as for example exploration on partial contexts. +
We introduce a schema for generating random formulas for different description logics, which extends an existing pattern for modal logics. Using the DL reasoners FaCT and RACER, we test the difficulty of these formulas, and it turns out that the properties that make a formula in an expressive DL hard are quite different from those known for ALC formulas. +
Recent research has shown that annotations are useful for representing access restrictions to the axioms of an ontology and their implicit consequences. Previous work focused on assigning a label, representing its access level, to each consequence from a given ontology. However, a security administrator might not be satisfied with the access level obtained through these methods. In this case, one is interested in finding which axioms would need to get their access restrictions modified in order to get the desired label for the consequence. In this paper we look at this problem and present algorithms for solving it with a variety of optimizations. We also present first experimental results on large scale ontologies, which show that our methods perform well in practice. +
A Generic Approach for Large-Scale Ontological Reasoning in the Presence of Access Restrictions to the Ontology's Axioms +
The framework developed in this paper can deal with scenarios where selected sub-ontologies of a large ontology are offered as views to users, based on criteria like the user's access right, the trust level required by the application, or the level of detail requested by the user. Instead of materializing a large number of different sub-ontologies, we propose to keep just one ontology, but equip each axiom with a label from an appropriate labeling lattice. The access right, required trust level, etc. is then also represented by a label (called user label) from this lattice, and the corresponding sub-ontology is determined by comparing this label with the axiom labels. For large-scale ontologies, certain consequence (like the concept hierarchy) are often precomputed. Instead of precomputing these consequences for every possible sub-ontology, our approach computes just one label for each consequence such that a comparison of the user label with the consequence label determines whether the consequence follows from the corresponding sub-ontology or not.
In this paper we determine under which restrictions on the user and axiom labels such consequence labels (called boundaries) always exist, describe different black-box approaches for computing boundaries, and present first experimental results that compare the efficiency of these approaches on large real-world ontologies. Black-box means that, rather than requiring modifications of existing reasoning procedures, these approaches can use such procedures directly as sub-procedures, which allows us to employ existing highly-optimized reasoners. +
This paper presents a generic data model and a rule-based query language for content based video access. The model allows user-defined attributes as well as explicit relations between object of interest. A declarative, rule-based query language is used to infer relationships about information represented in the model. +
Answering queries in information systems that allow for ex- pressive inferencing is currently a field of intense research. This problem is often referred to as ontology-based data ac- cess (OBDA). We focus on conjunctive query entailment un- der logical rules known as tuple-generating dependencies, existential rules or Datalog+/-. One of the most expressive decidable classes of existential rules known today is that of greedy bounded treewidth sets (gbts). We propose an algo- rithm for this class, which is worst-case optimal for data and combined complexities, with or without bound on the pred- icate arity. A beneficial feature of this algorithm is that it allows for separation between offline and online processing steps: the knowledge base can be compiled independently from queries, which are evaluated against the compiled form. Moreover, very simple adaptations of the algorithm lead to worst-case-optimal complexities for specific subclasses of gbts which have lower complexities, such as guarded rules. +
Trajectory data have been used in a variety of studies, including human behavior analysis, transportation management, and wildlife tracking. While each study area introduces a different perspective, they share the need to integrate positioning data with domain-specific information. Semantic annotations are necessary to improve discovery, reuse, and integration of trajectory data from different sources. Consequently, it would be beneficial if the common structure encountered in trajectory data could be annotated based on a shared vocabulary, abstracting from domain-specific aspects. Ontology design patterns are an increasingly popular approach to define such flexible and self-contained building blocks of annotations. They appear more suitable for the annotation of interdisciplinary, multi-thematic, and multi-perspective data than the use of foundational and domain ontologies alone. In this paper, we introduce such an ontology design pattern for semantic trajectories. It was developed as a community effort across multiple disciplines and in a data-driven fashion. We discuss the formalization of the pattern using the Web Ontology Language (OWL) and apply the pattern to two different scenarios, personal travel and wildlife monitoring. +
Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. The inexpressive Description Logic EL is of particular interest in this context since, on the one hand, several large biomedical ontologies are defined using EL. On the other hand, unification in EL has been shown to be NP-complete, and thus of significantly lower complexity than unification in other DLs of similarly restricted expressive power. Recently, a brute-force NP-unification algorithm for EL w.r.t. a restricted form of general concept inclusion axioms was developed. This paper introduces a goal-oriented algorithm that reduces the amount of nondeterministic guesses considerably. +
Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. For the DL EL, which is used to define several large biomedical ontologies, unification is NP-complete. A goal-oriented NP unification algorithm for EL that uses nondeterministic rules to transform a given unification problem into solved form has recently been presented. In this paper, we extend this goal-oriented algorithm in two directions: on the one hand, we add general concept inclusion axioms (GCIs), and on the other hand, we add role hierarchies (H) and transitive roles (R+). For the algorithm to be complete, however, the ontology consisting of the GCIs and role axioms needs to satisfy a certain cycle restriction. +
Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. For the DL EL, which is used to define several large biomedical ontologies, unification is NP-complete. A goal-oriented NP unification algorithm for EL that uses nondeterministic rules to transform a given unification problem into solved form has recently been presented. In this report, we extend this goal-oriented algorithm in two directions: on the one hand, we add general concept inclusion axioms (GCIs), and on the other hand, we add role hierarchies (H) and transitive roles (R+). For the algorithm to be complete, however, the ontology consisting of the GCIs and role axioms needs to satisfy a certain cycle restriction. +
A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL +
In two previous papers we have investigates the problem of computing the least common subsumer (lcs) and the most specific concept (msc) for the description logic EL in the presence of terminological cycles that are interpreted with descriptive semantics, which is the usual first-order semantics for description logics. In this setting, neither the lcs nor the msc needs to exist. We were able to characterize the cases in which the lcs/msc exists, but it was not clear whether this characterization yields decidability of the existence problem.
In the present paper, we develop a common graph-theoretic generalization of these characterizations, and show that the resulting property is indeed decidable, thus yielding decidability of the existence of the lcs and the msc. This is achieved by expressing the property in monadic second-order logic on infinite trees. We also show that, if it exists, then the lcs/msc can be computed in polynomial time. +
A Graph-Theoretic Generalization of the Least Common Subsumer and the Most Specific Concept in the Description Logic EL +
In two previous papers we have investigates the problem of computing the least common subsumer (lcs) and the most specific concept (msc) for the description logic EL in the presence of terminological cycles that are interpreted with descriptive semantics, which is the usual first-order semantics for description logics. In this setting, neither the lcs nor the msc needs to exist. We were able to characterize the cases in which the lcs/msc exists, but it was not clear whether this characterization yields decidability of the existence problem.
In the present paper, we develop a common graph-theoretic generalization of these characterizations, and show that the resulting property is indeed decidable, thus yielding decidability of the existence of the lcs and the msc. This is achieved by expressing the property in monadic second-order logic on infinite trees. We also show that, if it exists, then the lcs/msc can be computed in polynomial time. +
Plenty of novel emerging technologies are being proposed and evaluated today, mostly at the device and circuit levels. It is unclear what the impact of different new technologies at the system level will be. What is clear, however, is that new technologies will make their way into systems and will increase the already high complexity of heterogeneous parallel computing platforms, making it ever so difficult to program them. This paper discusses a programming stack for heterogeneous systems that combines and adapts well-understood principles from different areas, including capability-based operating systems, adaptive application runtimes, dataflow programming models, and model checking. We argue why we think that these principles built into the stack and the interfaces among the layers will also be applicable to future systems that integrate heterogeneous technologies. The programming stack is evaluated on a tiled heterogeneous multicore. +
We consider (first-order) query rewritability in the context of theory- mediated query answering. The starting point of our journey is the FUS/FES conjecture, which states that any theory that is a finite expansion set (FES) and admits query rewriting (BDD, FUS) must be uniformly bounded. We show that this conjecture holds for a large class of BDD theories, which we call “local”. Upon investigating how “non-local” BDD theories can actually get, we discover unexpected phenomena that, we think, are at odds with prevailing intuitions about BDD theories. +
A Katsuno-Mendelzon-Style Characterization of AGM Belief Base Revision for Arbitrary Monotonic Logics (Preliminary Report) +
The AGM postulates by Alchourron, Gärdenfors, and Makinson continue to represent a cornerstone in research related to belief change. We generalize the approach of Katsuno and Mendelzon (KM) for characterizing AGM base revision from propositional logic to the setting of (multiple) base revision in arbitrary monotonic logics. Our core result is a representation theorem using the assignment of total – yet not transitive – "preference" relations to belief bases. We also provide a characterization of all logics for which our result can be strengthened to preorder assignments (as in KM’s original work). +
A Logical Analysis of Instrumentality Judgments: Means-End Relations in the Context of Experience and Expectations +
This article proposes the use of temporal logic for an analysis of instrumentality inspired by the work of G.H. von Wright. The first part of the article contains the philosophical foundations: in particular, we discuss Von Wright’s general theory of agency and his account of instrumentality. Moreover, we provide several refinements of such framework via rigorous definitions of the core notions involved. In the second part, we develop a logical system called TLAE (Temporal Logic of Action and Expectations), which is inspired by a fragment of propositional dynamic logic and based on indeterministic time. We prove this system to be weakly complete relative to a given axiomatisation and then use it to formalise the instrumentality relations defined in the first part of the paper. Last, we point out some philosophical implications of our work and suggest ways in which our formalism could be employed in deontic settings. +
Ontology design patterns ease the engineering of ontologies, improvetheir quality, foster reusability, and support the alignment of ontologies by acting as common building blocks or strategies for reoccurring modeling problems. This makes ontology design patterns key enablers of semantic interoperability and, hence, a crucial technology for representing the body of knowledge of such heterogeneous domains as the geosciences. While different types of patterns can be distinguished, existing work on geo-ontology design patterns has solely focused on content patterns, i.e., design solutions for domain classes and relationships. In this work, we propose a logical pattern that addresses a frequent modeling problem that has hampered the development of sophisticated geo-ontologies in the past, namely how to model the quantification over types. We argue for the need for such a pattern, explain why it is difficult to model, demonstrate how to implement it using the Web Ontology Language OWL, and finally show how it can be applied to modeling concepts such as biodiversity. +
Description Logic Programs (DLP) have been described as a description logic (DL) that is in the "expressive intersection" of DL and datalog. This is a very weak guideline for defining DLP in a way that can be claimed to be optimal or maximal in any sense. Moreover, other DL fragments such as EL and Horn-SHIQ have also been "expressed" using datalog. So is DLP just one out of many equal DLs in this "expressive intersection"? This paper attempts to clarify these issues by characterising DLP with various design principles that clearly distinguish it from other approaches. A consequent application of the introduced principles leads to the definition of a significantly larger variant of DLP which we conjecture to be maximal in a concrete sense. A preliminary report on the proof of this maximality is provided. While DLP is used as a concrete (and remarkably complex) example in this paper, we argue that similar approaches can be applied to find canonical definitions for other fragments of logical languages, such as the "maximal" fragment of SWRL rules that can be expressed in the DL SROIQ. +
