- Implementation of an ontology-based stream processing system
The task is to implement a processing pipeline for event
recognition for stream data based on ontology
services. The task involves to identify a freely-available
data stream (e.g. weather data) and then implement a
databased approach to preprocessing the data such that it
can be used as instance data for a description logic query
answering system. Furthermore, the background ontology
that captures knowledge on the domain the data comes from
needs to be crafted.
Remark: This project is suited for students who need 8
SWS or for a group of students.
Tutor: Dr. Anni-Yasmin Turhan
- Testing Isomorphy of Formal Context with the VF2 algorithm
Testing isomorphy between two graphs is a well-researched
topic and many algorithms have been proposed. A
supposedly efficient algorithm for deciding isomorphy is
the VF2 algorithm [1]. The task is to understand, describe,
and present the VF2 algorithm for testing isomorphy
between two given graphs. As an application, the
algorithm should be applied to an experiment investigating
a statistical relationship between the number of intents
and the number of pseudo-intents of a formal context.
References:
- [1]
P. Foggia, C. Sansone, M. Vento: An Improved
Algorithm for Matching Large Graphs. Proceedings of
the 3rd IAPR-TC15 International Workshop on
Graph-based Representation, Italy, 2001.
Tutor: Dr. Daniel Borchmann
- Unification in Description logics
The system UEL can be used to detect redundancies in
ontologies by unifying concepts in the description logic
EL. In this project this system should be extended by a
newly developed rule-based approach which allows to
perform unification in regard of negative side conditions.
Remark: This project requires basic knowledge in description logics and good programming skills.
References
Tutor: Dr. Stefan Borgwardt
- Extending a system for the computation of logical difference
Aim of the project is to extend a system for recognizing
logical differences between ontologies, which is based on
a hypergraph representation of the ontologies [2]. The
extension is that not only differences regarding
subsumption should be detected, but also regarding
instance and conjunctive queries. Additionally, the system
should be extended to handle ontologies that are written
in the description logic EL plus role inclusions and
domain and range restrictions. A description of the
extended algorithm is available in [1].
Remark: This project requires basic knowledge
in description logics and in programming, particular in
JAVA.
References:
Tutor: Dr. Michel Ludwig
- Implementing algorithms to decide (k-)piecewise testability
A regular language is piecewise testable if its minimal
DFA satisfies several structural conditions. Nowadays,
there exist two quadratic algorithms to decide whether a
minimal DFA represents a piecewise testable language. The
first one, quadratic with respect to the number of states
of the DFA, is due to A. Trahtman [1], and the second one,
quadratic with respect to the size of the input alphabet,
is due to L. Polak and O. Klima [2]. The first part of this
project is to implement both methods and compare their
performance on a suitable selected set of input DFAs. In
the case a regular language is piecewise testable, it is
possible to find a minimal k (less then or equal to the
depth of the minimal DFA) for which the language is
k-piecewise testable (k-PT). The algorithms to do so are
described in [3] and [4]. The second part of the project
is to implement these tests, namely, when checking
k=0,1,2,3, the methods from [3], and for k>= 4 the method
of [4]. Since the problem for k>=4 is in general
coNP-complete, the point here is to look at the practical
limits of the algorithm. The input format for DFAs will be
specified (XML-like input).
References:
- [1] Trahtman, A.N., Piecewise and local threshold testability of DFA. FCT 2001, LNCS 2138, pp. 347-358.
- [2] Klima, O., Polak, L., Alternative automata characterization of piecewise testable languages. DLT 2013, LNCS 7907, pp. 289-300.
- [3] Masopust, T., Thomazo, M., On the Complexity of k-Piecewise Testability and the Depth of Automata, DLT 2015, LNCS 9168, pp. 364-376.
- [4] Klima, O., Kunc, M., Polak, L.: Deciding k-piecewise testability (manuscript)
Tutor: Dr. Thomas Masopust
- Implementing algorithms for piecewise
testable separability
Given two regular langauges (represented by NFAs),
the problem to decide whether there exists a piecewise
testable (PT) language (a regular language of a special
form) that separates the input languages has recently been
shown to be decidable in PTIME [1,2]. (More on the
motivation can be found there, too.) However, this
algorithm is not applicable to compute a PT language that
separates the input languages (called a separator). A
simple exponential algorithm to compute a separator has
been discussed in [3], which in the first phase also
decides the existence of a separator.
The aim of the project is to implement the PTIME algorithm
and the algorithm of [3] and to compare their performance on a
realistic sample of selected examples. Here the PTIME algorithm should
be compared with the first phase of algorithm of [3].
Then the separator should be computed using the algorithm of
[3]. This algorithm however supports implementations based
on minimal DFAs, NFAs and AFAs. All three approaches
should be implemented and their performance compared. This
requires not only to implement the structures to represent
DFAs, NFAs and AFAs, but also some of the classical and
some of the non-classical operations on languages. The
advantage is to keep the representations as small as
possible. This is easy for DFAs, but will require some
investigation for NFAs and AFAs.
The input format for NFAs will be specified (XML-like input).
Remark: This project is suited for students who need 8
SWS or for a group of students.
References:
- [1] Czerwinski, W., Martens, W., Masopust, T.,
Efficient Separability of Regular Languages by
Subsequences and Suffixes. ICALP 2013, LNCS 7966,
pp. 150-161
(http://arxiv.org/abs/1303.0966)
- [2] Place, T., Van Rooijen, L., Zeitoun, M.,
Separating Regular Languages by Piecewise Testable and
Unambiguous Languages. MFCS 2013, pp. 729-740
(http://arxiv.org/abs/1304.6734)
- [3] Holub, S., Masopust, T., Thomazo, M.,
Alternating Towers and Piecewise Testable Separators,
2014
(http://arxiv.org/abs/1409.3943)
Tutor: Dr. Thomas Masopust
- Investigating the complexity of deciding whether a minimal DFA
represents a 1-PT language
AC0 [1] is an important complexity class used in
circuit complexity, which is of interest in many fields of
theoretical computer science, such as database theory. The
aim of this project is to get acquainted with this class
and to show that the following problem belongs to this
class. The k-piecewise testable (k-PT) languages form a
subclass of regular languages that are characterized by a
few structural properties on their minimal DFAs. For 1-PT
languages, there are two simple structural properties
characterizing them [1]. The aim of the project is to show
that the problem to decide whether a minimal DFA
represents a 1-PT language belongs to AC0. In the case
the project goes well, the other question is to decide
whether the problem is also AC0-hard.
References:
Tutor: Dr. Thomas Masopust
-
Implementing most specific generalizations w.r.t. general TBoxes in ELGFP
This project aims at the implementation and evaluation of
methods for calculating least common subsumers and most
specific concepts in the leight-weight description logic
ELGFP, i.e. EL interpreted with greatest fixpoint
semantics. In contrast to standard EL with
descriptive semantics, those most specific generalizations
always exist in ELGFP and can be computed in polynomial
time. The student should furthermore make a comparison with
most specific generalizations w.r.t. standard descriptive
semantics and with role-depth bounded most specific
generalizations w.r.t descriptive semantics, both of these approaches have recently been implemented.
Remark: Basic knowledge in description logics and good programming
skills are expected. For an easier handling and integration
with existing software (e.g. ELK, Protege etc.), the program
should be built on top of the OWL API.
References:
Tutor: Francesco Kriegel
-
Formal concept analysis & propositional logic: from pseudo-intents to implicational bases
This project’s aim is the formulation of a minimal theory of
implications, which holds in a given set of propositional
models and furthermore entails all other implications, that
hold in the given model set. This requires an isomorphism
between propositional model sets and formal contexts, to
adapt the existing results for implicational bases of formal
contexts. Furthermore the student should give an algorithm to
compute the implicational base. The results can be extended
to propositional bases.
Remark: Basic knowledge in propositional logic and
set theory is expected. Further knowledge in logic and order
theory may be helpful.
References:
- Bernhard Ganter & Rudolf Wille: Formal Concept Analysis
- Bernhard Ganter: Attribute Exploration with Background Knowledge
Tutor: Francesco Kriegel
![[TU Dresden]](/pics/tu-logo.gif){kind=logo}