Chair for Automata Theory
of the Institute for Theoretical Computer Science,
Faculty of Computer Science at
TU Dresden
Technical Reports
1997
F. Baader and U. Sattler.
Description Logics with Aggregates and Concrete Domains.
LTCS-Report 97-01, LuFg Theoretical Computer Science, RWTH Aachen, Germany,
1997.
An abridged version has appeared in the Proceedings of the International
Workshop on Description Logics 97.
Bibtex entry Paper (PS)
Abstract
We show that extending description logics by simple aggregation functions
as available in database systems may lead to undecidability of inference problems
such as satisfiability and subsumption.
F. Baader and P. Narendran.
Unification of Concept Terms in Description Logics.
LTCS-Report 97-02, LuFg Theoretical Computer Science, RWTH Aachen, Germany,
1997.
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.
F. Baader.
On the Complexity of Boolean Unification.
LTCS-Report 97-03, LuFg Theoretical Computer Science, RWTH Aachen, Germany,
1997.
Bibtex entry Paper (PS)
Abstract
Unification modulo the theory of Boolean algebras has been investigated
by several autors. Nevertheless, the exact complexity of the decision problem
for unification with constants and general unification was not
known. In this research note, we show that the decision problem is
$\Pi^p_2$-complete for unification with constants and
PSPACE-complete for general unification. In contrast, the decision
problem for elementary unification (where the terms to be unified
contain only symbols of the signature of Boolean algebras) is
``only'' NP-complete.
R. Küsters.
Characterizing the semantics of terminological cycles in ALN
using finite automata.
LTCS-Report 97-04, LuFg Theoretical Computer Science, RWTH Aachen, Germany,
1997.
Bibtex entry Paper (PS)
Abstract
The representation of terminological knowledge may naturally lead to terminological cycles. In
addition to descriptive semantics, the meaning of cyclic terminologies can
also be captured by fixed-point semantics, namely, greatest and least
fixed-point semantics. To gain a more profound understanding
of these semantics and to obtain inference algorithms as well as complexity
results for inconsistency, subsumption, and
related inference tasks, this paper provides automata theoretic
characterizations of these semantics. More precisely,
the already existing results for FL_0 are extended to the language ALN, which
additionally allows for primitive negation and number-restrictions.
Unlike FL_0, the language ALN can express inconsistent concepts, which
makes non-trivial extensions of the characterizations and algorithms
necessary. Nevertheless, the complexity of reasoning does not increase when
going from FL_0 to ALN. This distinguishes ALN from the very
expressive languages with fixed-point operators proposed in the literature. It
will be shown, however, that cyclic ALN-terminologies are expressive enough to capture
schemata in certain semantic data models.
M. S. Hacid, P. Marcel, and C. Rigotti.
A rule based data manipulation language for OLAP systems.
LTCS-Report 97-05, LuFg Theoretical Computer Science, RWTH Aachen, 1997.
A short version has appeared in the Proceedings of the 5th International
Conference on Deductive and Object-Oriented Databases (DOOD'97), Montreux,
Switzerland.
Bibtex entry Paper (PS)
Abstract
This paper proposes an extension of Datalog
devoted to data manipulations in On-Line
Analytical Processing (OLAP) systems.
This language provides a declarative and concise
way to specify the basic standard restructuring and summarizing operations
on multidimensional cubes used in these systems.
We define its model-theoretic semantics and
an equivalent fixpoint semantics that leads to a naive evaluation
procedure.
We also illustrate its applicability to specify usefull more complex
data manipulations arising in OLAP systems.
There is also a complete overview of our technical reports.
Back to the homepage of the Chair for Automata Theory.
Generated at Fri Jun 12 11:21:13 CEST 2009.