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: Anni-Yasmin Turhan

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.

Remarks: This project requires basic knowledge in description logics and good programming skills.

References:

• UEL: http://uel.sourceforge.net/
• Report: http://lat.inf.tu-dresden.de/research/reports/2015/BaBM-LTCS-15-03.pdf

Tutor: Stefan Borgwardt

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,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: Tomáš Masopust

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: Tomáš Masopust

One of the main research focuses of Formal Concept Analysis (FCA) is the study of the implicational theory of formal contexts. Many important results have been obtained in this line of research that are also relevant to other research fields where implications play some role. On the other hand, there are also results from related fields that are potentially important to research in FCA. The goal of this project is to investigate one of these topics and to translate it into the language of FCA.

The paper that should be considered in this project is the (rather old) work by Kautz, Kearns, and Selman on “Horn Approximation of Empirical Data”. The task is to read this paper and to produce a written report about the results of this publication that uses standard FCA terminology. An optional additional task is to implement some of the algorithms presented in that work in a standard FCA software.

Tutor: Daniel Borchmann

From a complexity point of view, reasoning with implications directly is very easy. Nevertheless, researchers have investigated alternative approaches for this task. One of these is the model-based approach, in which (using the language of Formal Concept Analysis) from a given set Σ of implications a (minimal) formal context 𝕂 is constructed such that the valid implications of 𝕂 are exactly the implications entailed by Σ. It can indeed happen that the formal context 𝕂 is considerably smaller than Σ, so that reasoning with 𝕂 instead of Σ is practical. A closely related notion from database theory is the one of “Armstrong Relations”.

The goal of this project is to investigate existing literature for approaches to turn the set Σ into a formal context 𝕂 as described above. Optionally, those methods can be implemented and experimentally evaluated.

Tutor: Daniel Borchmann

Formal Concept Analysis (FCA) was developed as an attempt to formalize the philosophical notion of a "concept". In particular, it has a strong correspondence to propositional logic, and provides methods for handling implicational knowledge. As a famous example, the canonical base of a given formal context 𝕂 is a minimal implication set which is sound and complete for the implicational knowledge of 𝕂. For the entailment relation between implication sets both a semantic and several equivalent syntactic characterizations exist.

Recently, a probabilistic extension of FCA was investigated, and especially a technique for the axiomatization of implications over probabilistic attributes was introduced. However, the implicational entailment was only described semantically, and no sound and complete syntactic deduction method exists. The goal of this project is to find such a syntactic characterization, and - if there is enough time left - to provide an appropriate implementation.

Tutor: Francesco Kriegel

Formal Concept Analysis (FCA) was developed as an attempt to formalize the philosophical notion of a "concept". In particular, it has a strong correspondence to propositional logic, and provides methods for handling implicational knowledge. As a famous example, the canonical base of a given formal context 𝕂 is a minimal implication set which is sound and complete for the implicational knowledge of 𝕂.

A cellular automaton (CA) is a set of cells together with a neighborhood relation and transition rules, which describe the evolution of the cells depending on the state of the neighboring cells. In the simplest setting, a cell can either be dead or alive, and the cells are arranged in a grid. The task of this project is to investigate whether methods from FCA can be used to explore the transition rules of a cellular automaton when some observations of the CA at different time instants have been collected.

Tutor: Francesco Kriegel

This project’s aim is the formulation of a minimal theory of implications that 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