Chair for Automata Theory
of the Institute for Theoretical Computer Science,
Faculty of Computer Science at
TU Dresden
Technical Reports
2010
Franz Baader, Marcel Lippmann, and Hongkai Liu.
Adding Causal Relationships to DL-based Action Formalisms.
LTCS-Report 10-01, Chair of Automata Theory, Institute of Theoretical Computer
Science, Technische Universität Dresden, Dresden, Germany, 2010.
See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry Paper (PDF)
Abstract
In the reasoning about actions community, causal relationships have been proposed
as a possible approach for solving the ramification problem, i.e., the problem
of how to deal with indirect effects of actions. In this paper, we show that
causal relationships can be added to action formalisms based on Description Logics
without destroying the decidability of the consistency and the projection problem.
Rafael Peñaloza and Anni-Yasmin Turhan.
Completion-based computation of least common subsumers with limited
role-depth for EL and Prob-EL^01.
LTCS-Report 10-02, Chair for Automata Theory, Institute for Theoretical
Computer Science, Dresden University of Technology, Germany, 2010.
See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry Paper (PS) Paper (PDF)
Abstract
The least common subsumer (lcs) w.r.t general EL-TBoxes does not
need to exists in general due to cyclic axioms. In this report we
present an algorithm for computing role-depth bounded EL-lcs based
on the completion algorithm for EL. We extend this computation
algorithm to a recently introduced probabilistic variant of EL:
Prob-EL-01.
Rafael Peñaloza and Anni-Yasmin Turhan.
Completion-based computation of most specific concepts with limited
role-depth for EL and Prob-EL^01.
LTCS-Report 10-03, Chair for Automata Theory, Institute for Theoretical
Computer Science, Dresden University of Technology, Germany, 2010.
See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry Paper (PS) Paper (PDF)
Abstract
In Description Logics the reasoning service most specific concept
(msc) constructs a concept description that generalizes an ABox
individual into a concept description. For the Description Logic EL
the msc may not exist, if computed with respect to general
EL-TBoxes or cyclic ABoxes. However, it is still possible to find
a concept description that is the msc up to a fixed role-depth,
i.e. with respect to a maximal nesting of quantifiers. In this
report we present a practical approach for computing the role-depth
bounded msc, based on the polynomial-time completion algorithm for
EL. We extend these methods to ProbEL-01, which is a probabilistic
variant of EL. Together with the companion report
LTCS-10-02 this report devises computation methods for the
bottom-up construction of knowledge bases for EL and ProbEL-01.
Franz Baader and Barbara Morawska.
SAT Encoding of Unification in EL.
LTCS-Report 10-04, Chair of Automata Theory, Institute of Theoretical Computer
Science, Technische Universität Dresden, Dresden, Germany, 2010.
See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry Paper (PDF)
Abstract
The Description Logic EL is an inexpressive knowledge representation language,
which nevertheless has recently drawn considerable attention in the knowledge representation
and the ontology community since, on the one hand, important inference problems such as
the subsumption problem are polynomial. On the other hand, EL
is used to define large biomedical ontologies. Unification in
Description Logics has been proposed as a novel inference
service that can, for example, be used to detect redundancies
in ontologies.
In a recent paper, we have shown that unification in EL
is NP-complete, and thus of a complexity that is considerably lower
than in other Description Logics of comparably restricted expressive power.
In this paper, we introduce a new NP-algorithm for solving unification problem in EL,
which is based on a reduction to satisfiability in propositional logic (SAT).
The advantage of this new algorithm is, on the one hand, that it allows us to employ
highly optimized state of the art SAT solvers when implementing an EL-unification algorithm.
On the other hand, this reduction provides us with a proof of the fact that EL-unification
is in NP that is much simpler than the one given in our previous paper on EL-unification.
Stefan Borgwardt and Rafael Peñaloza.
Complementation and Inclusion of Weighted Automata on Infinite Trees.
LTCS-Report 10-05, Chair for Automata Theory, Institute for Theoretical
Computer Science, Dresden University of Technology, Germany, 2010.
See http://lat.inf.tu-dresden.de/research/reports.html.
Bibtex entry Paper (PDF)
Abstract
Weighted automata can be seen as a natural generalization of finite state automata to more
complex algebraic structures. The standard reasoning tasks for unweighted automata can also
be generalized to the weighted setting. In this report we study the problems of
intersection, complementation and inclusion for weighted automata on infinite trees and
show that they are not harder than reasoning with unweighted automata. We also present explicit
methods for solving these problems optimally.
There is also a complete overview of our technical reports.
Back to the homepage of the Chair for Automata Theory.
Generated at Mon Jan 30 16:30:34 CET 2012.