Chair for Automata Theory of the Institute for Theoretical Computer Science, Faculty of Computer Science at TU Dresden

Technical Reports

2002

 C. Lutz. Reasoning about Entity Relationship Diagrams with Complex Attribute Dependencies. LTCS-Report 02-01, LuFG Theoretical Computer Science, RWTH Aachen, Germany, 2002. See http://www-lti.informatik.rwth-aachen.de/Forschung/Reports.html.
Bibtex entry  Paper (PS)

Abstract

Entity Relationship (ER) diagrams are among the most popular formalisms for the support of database design. To aid database designers in building (extended) ER schemas, Description Logics (DLs) have been proposed and successfully used as a tool for reasoning about such schemas. In this paper, we propose the extension of ER diagrams with dependencies on attributes and show how such dependencies can be translated into DLs with concrete domains. The result is an integrated approach to reasoning with conceptual models and attribute dependencies.

F. Baader. Terminological Cycles in a Description Logic with Existential Restrictions. LTCS-Report 02-02, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2002. See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry  Paper (PS)

Abstract

Cyclic definitions in description logics have until now been investigated only for description logics allowing for value restrictions. Even for the most basic language FL0, which allows for conjunction and value restrictions only, deciding subsumption in the presence of terminological cycles is a PSPACE-complete problem. This report investigates subsumption in the presence of terminological cycles for the language EL, which allows for conjunction and existential restrictions. In contrast to the results for FL0, subsumption in EL remains polynomial, independent of whether we use least fixpoint semantics, greatest fixpoint semantics, or descriptive semantics. These results are shown via a characterization of subsumption through the existence of certain simulation relations between nodes of the description graph associated with a given cyclic terminology.

S. Brandt and A.-Y. Turhan. An Approach for Optimizing ALE-Approximation of ALC-Concepts. LTCS-Report 02-03, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2002. See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry  Abstract  Paper (PS)

Abstract

An approximation of an ALC-concept by an ALE-concept can be computed in double exponential time. Consequently, one needs powerful optimization techniques for approximating an entire unfoldable TBox. Addressing this issue we identify a special form of ALC-concepts, which can be divided into parts s.t. each part can be approximated independently. This independent approximation in turn facilitates caching during the computation of approximation.

C. Lutz, C. Areces, I. Horrocks, and U. Sattler. Keys, Nominals, and Concrete Domains. LTCS-Report 02-04, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2002. See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry  Abstract  Paper (PS)

Abstract

Many description logics (DLs) combine knowledge representation on an abstract, logical level with an interface to "concrete" domains such as numbers and strings with built-in predicates such as <, +, and prefix-of. These hybrid DLs have turned out to be quite useful for reasoning about conceptual models of information systems, and as the basis for expressive ontology languages. We propose to further extend such DLs with key constraints that allow the expression of statements like "US citizens are uniquely identified by their social security number". Based on this idea, we introduce a number of natural description logics and perform a detailed analysis of their decidability and computational complexity. It turns out that naive extensions with key constraints easily lead to undecidability, whereas more careful extensions yield NExpTime-complete DLs for a variety of useful concrete domains.

C. Lutz, U. Sattler, and L. Tendera. The Complexity of Finite Model Reasoning in Description Logics. LTCS-Report 02-05, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2002. See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry  Abstract  Paper (PS)

Abstract

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.

I. Horrocks and U. Sattler. Decidability of SHIQ with Complex Role Inclusion Axioms. LTCS-Report 02-06, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2002. See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry  Abstract  Paper (PS)

Abstract

Motivated by medical terminology applications, we investigate the decidability of an expressive and prominent DL, SHIQ, extended with role inclusion axioms of the form R o S => T (where "o" denotes composition of binary relations). It is well-known that a naive such extension leads to undecidability, and thus we restrict our attention to axioms of the form R o S => R or S o R => R, which is the most important form of axioms in the applications that motivated this extension. Surprisingly, this extension is still undecidable. However, it turns out that restricting our attention further to acyclic sets of such axioms, we regain decidability. We present a tableau-based decision procedure for this DL and report on its implementation, which behaves well in practise and provides important additional functionality in a medical terminology application.

F. Baader. Least Common Subsumers, Most Specific Concepts, and Role-Value-Maps in a Description Logic with Existential Restrictions and Terminological Cycles. LTCS-Report 02-07, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, Germany, 2002. See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry  Paper (PS)

Abstract

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.

There is also a complete overview of our technical reports.
home Back to the homepage of the Chair for Automata Theory.
Generated at Fri Jun 12 11:21:13 CEST 2009.