We make a first step towards adapting an existing approach for privacy-preserving publishing of linked data to Description Logic (DL) ontologies. We consider the case where both the knowledge about individuals and the privacy policies are expressed using concepts of the DL EL , which corresponds to the setting where the ontology is an EL instance store. We introduce the notions of compliance of a concept with a policy and of safety of a concept for a policy, and show how optimal compliant (safe) generalizations of a given EL concept can be computed. In addition, we investigate the complexity of the optimality problem.

Concrete domains have been introduced in the area of Description Logic to enable reference to concrete objects (such as numbers) and predefined predicates on these objects (such as numerical comparisons) when defining concepts. Unfortunately, in the presence of general concept inclusions (GCIs), which are supported by all modern DL systems, adding concrete domains may easily lead to undecidability. To regain decidability of the DL ALC in the presence of GCIs, quite strong restrictions, in sum called ω-admissibility, were imposed on the concrete domain. On the one hand, we generalize the notion of ω-admissibility from concrete domains with only binary predicates to concrete domains with predicates of arbitrary arity. On the other hand, we relate ω-admissibility to well-known notions from model theory. In particular, we show that finitely bounded homogeneous structures yield ω-admissible concrete domains. This allows us to show ω-admissibility of concrete domains using existing results from model theory. When integrating concrete domains into lightweight DLs of the E L family, achieving decidability is not enough. One wants reasoning in the resulting DL to be tractable. This can be achieved by using so-called p-admissible concrete domains and restricting the interaction between the DL and the concrete domain. We investigate padmissibility from an algebraic point of view. Again, this yields strong algebraic tools for demonstrating p-admissibility. In particular, we obtain an expressive numerical p-admissible concrete domain based on the rational numbers. Althoughω-admissibility and p-admissibility are orthogonal conditions that are almost exclusive, our algebraic characterizations of these two properties allow us to locate an infinite class of p-admissible concrete domains whose integration into ALC yields decidable DLs.

The description logic ALCQI extends the 'standard' description logic ALC by qualifying number restrictions and converse roles. We show that concept satisfiability for this DL is still decidable in polynomial space. The presented algorithm combines techniques from [Tob99] to deal with qualifying number restrictions and from [HST99] to deal with converse roles.

Aus der Einleitung: „As widely argued [Horrocks&Gough,1997; Sattler,1996], transitive roles play an important role in the adequate representation of aggregated objects: they allow these objects to be described by referring to their parts without specifying a level of decomposition. In [Horrocks&Gough,1997], the Description Logic (DL) ALCHR+ is presented, which extends ALC with transitive roles and a role hierarchy. It is argued in [Sattler,1998] that ALCHR+ is well-suited to the representation of aggregated objects in applications that require various part-whole relations to be distinguished, some of which are transitive. However, ALCHR+ allows neither the description of parts by means of the whole to which they belong, or vice versa. To overcome this limitation, we present the DL ALCHIR+ which allows the use of, for example, has part as well as is part of. To achieve this, ALCHR+ was extended with inverse roles. It could be argued that, instead of defining yet another DL, one could make use of the results presented in [De Giacomo&Lenzerini,1996] and use ALC extended with role expressions which include transitive closure and inverse operators. The reason for not proceeding like this is the fact that transitive roles can be implemented more eficiently than the transitive closure of roles (see [Horrocks&Gough,1997]), although they lead to the same complexity class (ExpTime-hard) when added, together with role hierarchies, to ALC. Furthermore, it is still an open question whether the transitive closure of roles together with inverse roles necessitates the use of the cut rule [DeGiacomo&Massacci,1998], and this rule leads to an algorithm with very bad behaviour. We will present an algorithm for ALCHIR+ without such a rule.” / An abridged version will appear in the Proceedings of the International Workshop on Description Logics, Trento, Italy, 1998.

Matching of concepts against patterns is a new inference task in Description Logics, which was originally motivated by applications of the CLASSIC system. Consequently, the work on this problem was until now mostly concerned with sublanguages of the Classic language, which does not allow for existential restrictions. Motivated by an application in chemical process engineering, which requires a description language with existential restrictions, this paper investigates the matching problem in Description Logics with existential restrictions. It turns out that existential restrictions make matching more complex in two respects. First, whereas matching in sublanguages of CLASSIC is polynomial, deciding the existence of matchers is an NP-complete problem in the presence of existential restrictions. Second, whereas in sublanguages of Classic solvable matching problems have a unique least matcher, this is not the case for languages with existential restrictions. Thus, it is not a priori clear which of the (possibly infinitely many) matchers should be returned by a matching algorithm. After determining the complexity of the decision problem, the present paper first investigates the question of what are 'interesting' sets of matchers, and then describes algorithms for computing these sets for the languages EL (which allows for conjunction and existential restrictions) and ALE (which additionally allows for value restrictions, primitive negation, and the bottom concept). / An abridged version of this technical report has been submitted to KR 2000.

No description available.

We investigate the computational complexity of several decision, enumeration and counting problems related to pseudo-intents. We show that given a formal context and a set of its pseudo-intents, checking whether this context has an additional pseudo-intent is in conp and it is at least as hard as checking whether a given simple hypergraph is saturated. We also show that recognizing the set of pseudo-intents is also in conp and it is at least as hard as checking whether a given hypergraph is the transversal hypergraph of another given hypergraph. Moreover, we show that if any of these two problems turns out to be conp-hard, then unless p = np, pseudo-intents cannot be enumerated in output polynomial time. We also investigate the complexity of finding subsets of a given Duquenne-Guigues Base from which a given implication follows. We show that checking the existence of such a subset within a specified cardinality bound is np-complete, and counting all such minimal subsets is #p-complete.

Axiom pinpointing has been introduced in description logics (DLs) to help the user to understand the reasons why consequences hold and to remove unwanted consequences by computing minimal (maximal) subsets of the knowledge base that have (do not have) the consequence in question. The pinpointing algorithms described in the DL literature are obtained as extensions of the standard tableau-based reasoning algorithms for computing consequences from DL knowledge bases. Although these extensions are based on similar ideas, they are all introduced for a particular tableau-based algorithm for a particular DL. The purpose of this paper is to develop a general approach for extending a tableau-based algorithm to a pinpointing algorithm. This approach is based on a general definition of „tableaux algorithms,' which captures many of the known tableau-based algorithms employed in DLs, but also other kinds of reasoning procedures.

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.

Entity Relationship (ER) diagrams are among the most popular formalisms for the support of database design [7, 12, 17, 6]. Their classical use in the (usually computer aided) database design process can roughly be described as follows: after evaluating the requirements of the application, the database designer constructs an ER schema, which represents the conceptual model of the new database. CASE tools can be used to automatically transform the ER schema into a relational database schema, which is then manually fine-tuned. During the last years, the initially rather simple ER formalisms has been extended by various means of expressivity to account for new, more complex application areas such as schema integration for data warehouses [12, 3, 13]. Designing a conceptual model with such enriched ER diagrams is a nontrivial task: there exist complex interactions between the various means of expressivity, which quite often result in unnoticed inconsistencies in the ER schemas and in implicit ramifications of the modeling that have not been intended by the designer. To address this problem, Description Logics (DLs) have been proposed and succesfully used as a tool for reasoning about ER diagrams and thereby detecting the aforementioned anomalies [5, 6, 8].