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

Technical Reports

1998

 C.B. Tresp and R. Molitor. A Description Logic for Vague Knowledge. LTCS-Report 98-01, LuFg Theoretical Computer Science, RWTH Aachen, Germany, 1998. See http://www-lti.informatik.rwth-aachen.de/Forschung/Reports.html.
Bibtex entry  Abstract  Paper (PS)

Abstract

This work introduces the concept language ALC(FM) which is an extension of ALC to many-valued logics. ALC(FM) allows to express vague concepts, e.g. `more or less enlarged' or `very small'. To realize this extension to many-valued logics, the classical notions of satisfiability and subsumption had to be modified appropriately. For example, ALC(FM)-concepts are no longer either satisfiable or unsatisfiable, but they are satisfiable to a certain degree. The main contribution of this paper is a sound and complete method for computing the degree of subsumption between two ALC(FM)-concepts.

F. Baader and U. Sattler. Description Logics with Aggregates and Concrete Domains, Part II (extended). LTCS-Report 98-02, LuFg Theoretical Computer Science, RWTH Aachen, Germany, 1998.
Bibtex entry  Paper (PS)

R. Molitor. Structural Subsumption for ALN. LTCS-Report 98-03, LuFG Theoretical Computer Science, RWTH Aachen, Germany, 1998.
Bibtex entry  Paper (PS)

F. Baader, R. Küsters, and R. Molitor. Structural Subsumption Considered from an Automata Theoretic Point of View. LTCS-Report 98-04, LuFG Theoretical Computer Science, RWTH Aachen, Germany, 1998. See http://www-lti.informatik.rwth-aachen.de/Forschung/Reports.html.
Bibtex entry  Paper (PS)

Abstract

This paper compares two approaches for deriving subsumption algorithms for the description logic ALN: structural subsumption and an automata-theoretic characterization of subsumption. It turns out that structural subsumption algorithms can be seen as special implementations of the automata-theoretic characterization.

I. Horrocks and U. Sattler. A Description Logic with Transitive and Converse Roles and Role Hierarchies. LTCS-Report 98-05, LuFg Theoretical Computer Science, RWTH Aachen, Germany, 1998.
Bibtex entry  Paper (PS)

F. Baader and R. Küsters. Computing the least common subsumer and the most specific concept in the presence of cyclic ALN-concept descriptions. LTCS-Report 98-06, LuFg Theoretical Computer Science, RWTH Aachen, Germany, 1998.
Bibtex entry  Abstract  Paper (PS)

Abstract

Computing least common subsumers (lcs) and most specific concepts (msc) are inference tasks that can be used to support the ``bottom up'' construction of knowledge bases for KR systems based on description logic. For the description logic ALN, the msc need not always exist if one restricts the attention to acyclic concept descriptions. In this paper, we extend the notions lcs and msc to cyclic descriptions, and show how they can be computed. Our approach is based on the automata-theoretic characterizations of fixed-point semantics for cyclic terminologies developed in previous papers.

F. Baader and P. Narendran. Unification of Concept Terms in Description Logics: Revised Version. LTCS-Report 98-07, LuFg Theoretical Computer Science, RWTH Aachen, Germany, 1998.
Bibtex entry  Abstract  Paper (PS)

Abstract

Unification of concept terms is a new kind of inference problem for Description Logics, which extends the equivalence problem by allowing to substitute certain concept names by concept terms before testing for equivalence. We show that this inference problem is of interest for applications, and present first decidability and complexity results for a small concept description language. This is a revised version of LTCS-Report 97-02: it provides a stronger complexity result in Section 6.

I. Horrocks, U. Sattler, and S. Tobies. A PSpace-algorithm for deciding ALCNI_R^+-satisfiability. LTCS-Report 98-08, LuFG Theoretical Computer Science, RWTH Aachen, 1998.
Bibtex entry  Paper (PS)

Abstract

ALCI_{R^+}---ALC augmented with transitive and inverse roles---is an expressive Description Logic which is especially well-suited for the representation of complex, aggregated objects. Despite its expressiveness, it has been conjectured that concept satisfiability for this logic could be decided in a comparatively efficient way. In this paper we prove the correctness of this conjecture by presenting a PSpace algorithm for deciding satisfiability and subsumption of ALCI_{R^+}-concepts. The space-efficiency of this tableau-based algorithm is due to a sophisticated guidance of the search for a solution. This algorithm will be the basis for an efficient implementation.

F. Baader, R. Küsters, and R. Molitor. Computing Least Common Subsumers in Description Logics with Existential Restrictions. LTCS-Report 98-09, LuFG Theoretical Computer Science, RWTH Aachen, Germany, 1998. See http://www-lti.informatik.rwth-aachen.de/Forschung/Papers.html.
Bibtex entry  Paper (PS)

Abstract

Computing least common subsumers (lcs) is an inference task that can be used to support the "bottom-up" construction of knowledge bases for KR systems based on description logics. Previous work on how to compute the lcs has concentrated on description logics that allow for universal value restrictions, but not for existential restrictions. The main new contribution of this paper is the treatment of description logics with existential restrictions. More precisely, we show that, for the description logic ALE (which allows for conjunction, universal value restrictions, existential restrictions, negation of atomic concepts, as well as the top and the bottom concept), the lcs always exists and can effectively be computed. Our approach for computing the lcs is based on an appropriate representation of concept descriptions by certain trees, and a characterization of subsumption by homomorphisms between these trees. The lcs operation then corresponds to the product operation on trees.

F. Baader, R. Molitor, and S. Tobies. The Guarded Fragment of Conceptual Graphs. LTCS-Report 98-10, LuFG Theoretical Computer Science, RWTH Aachen, Germany, 1998. See http://www-lti.informatik.rwth-aachen.de/Forschung/Papers.html.
Bibtex entry  Abstract  Paper (PS)

Abstract

Conceptual graphs (CGs) are an expressive and intuitive formalism, which plays an important role in the area of knowledge representation. Due to their expressiveness, most interesting problems for CGs are inherently undecidable. We identify the syntactically defined guarded fragment of CGs, for which both subsumption and validity is decidable in deterministic exponential time.

F. Baader, R. Molitor, and S. Tobies. On the Relation between Descripion Logics and Conceptual Graphs. LTCS-Report 98-11, LuFG Theoretical Computer Science, RWTH Aachen, Germany, 1998. See http://www-lti.informatik.rwth-aachen.de/Forschung/Reports.html.
Bibtex entry  Paper (PS)

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.