Topics for Theses and Projects
Our topics for bachelor and master theses as well as projects are from the areas of software engineering and programming languages. The concrete topics for theses are based on our research interests and allow students to make their own contribution to a field of research. Our main target group are students of Computer Science, Software Engineering, Media Informatics, Artificial Intelligence, and Cognitive Systems.
This page offers a selection of topics and subject areas. For more information, please do not hesitate to contact the respective supervisor. In addition, we are open to your own suggestions for topics.
(Legend - B: Bachelor Thesis, M: Master Thesis, P: Project)
Outline of a Bachelor or Master Thesis
Topic and Proposal
After the initial contact, the topic and the contents of the Bachelor or Master thesis are agreed upon and recorded in a proposal. The proposal has proven to be a valueable tool for risk minimization and planning of the thesis and includes:
- the context of the thesis
- the research question
- the state of research
- the solution idea
- the methodology and the evaluation plan
Much of the proposal can be reused in the final thesis.
Interim Presentation
In the course of the interim presentation, students learn to present and communicate results. In addition, the interim presentation can be used to reflect on the status of the thesis so far and to respond to feedback.
Submission and Final Presentation
The submission of the final thesis and the final presentation formally conclude the bachelor or master thesis.
(Legend - B: Bachelor thesis, M: Master thesis, P: Project)
Human-centered Software Engineering
Enhancing Collaborative Modeling
Context
We are convinced that (graphical) modeling is a cooperative and explorative process done by domain experts. However, several studies identified an insufficient collaboration support of graphical modeling tools. Therefore, we develop a new collaboration approach for graphical modeling tools that is based on the persistence of sequential edit operations (also called operation-based approach). We aim to enable both synchronous as well as asynchronous collaboration and improve the comprehensibility of evolving models.
Problem
At the present stage of our research we persist every kind of edit operation a user has performed to alter the model and present the result in a simple directed acyclic graph (DAG). We are able to filter the edit history by the type of operation or the target of an operation. However, we can not formulate more advanced queries. For instance: "Show only refactoring operations performed by Alice during the last two weeks within this area of the model."
Tasks
- Develop or extend query language (QL) covers the following dimensions:
- Syntax, e.g., type of element
- Semantic, e.g., fulfilment of a requirement
- Meta information, e.g., time or user
- Edit operations, e.g., type of edit operation
- QL should be interactive and should provide live feedback.
- Conduct a user study to evaluate the user experience of your implementation.
Related Work
- Enhancing Collaborative Modeling
Summary of the vision of our new modeling approach. - Improving the Comprehension of Evolving Graphical Models
Visual tools and their evaluation to support domain experts to understand how, why, what, and by whom a model was changed over time. - Event Sourcing
Data persistence pattern that we use for versioning purposes. - A Domain-Specific Language and Interactive User Interface for Model-Driven Engineering of Technology Roadmaps
Graphical roadmapping tool developed by our institute that we extend with our collaboration approach.
Contact
Context
We are convinced that (graphical) modeling is a cooperative and explorative process done by domain experts. However, several studies identified an insufficient collaboration support of graphical modeling tools. Therefore, we develop a new collaboration approach for graphical modeling tools that is based on the persistence of sequential edit operations (also called operation-based approach). We aim to enable both synchronous as well as asynchronous collaboration and improve the comprehensibility of evolving models.
Problem
In the context of synchronous collaboration it can happen that two or more users make changes within the same area of a graphical model. This might lead to visually interfering edit operations, e.g., Alice edits the value of a property Prop1 while Bob moves BlockA which contains Prop1. Also semantically conflicting edit operations, such as Bob deletes BlockA instead of moving it, can have a negative impact to the user experience.
We assume that the negative impact of those interfering edit operations can be avoided be implicitly create a temporary branch that delays interfering edit operations of other users.
Tasks
- Systematically identify different types of be interfering edit operations
- Develop an algorithm to detect interfering edit operations
- Implement a solution that uses your algorithm and is able to temporary delay other users edit operations.
- Conduct a user study that evaluates the impact of your approach on the user experience.
Related Work
- Enhancing Collaborative Modeling
Summary of the vision of our new modeling approach. - An Operation-based Versioning Approach for Synchronous and Asynchronous Collaboration in Graphical Modeling Tools.
Developed operation-based versioning approach. - An Introduction to Model Versioning
Introduction in model versioning. - Event Sourcing
Data persistence pattern that we use for versioning purposes. - A Domain-Specific Language and Interactive User Interface for Model-Driven Engineering of Technology Roadmaps
Graphical roadmapping tool developed by our institute that we extend with our collaboration approach.
Contact
Relaxed Conformance Editing
Context
Graphical modeling is a widely used task in software and systems engineering. Similar to how an IDE assists with programming, graphical modeling tools are intended to help create models as efficiently as possible.
Basically, two types of graphical modeling tools can be distinguished: Either the tool is tailored to a graphical language and restricts the user in drawing in such a way that only syntactically correct models can be drawn (correct-by-constructionn approach), or one has a pure drawing tool that offers no language-specific support but allows maximum freedom. As so often, the optimum lies somewhere in between.
Problem
In this master thesis, a prototypical implementation of a graphical modeling tool in React is to be adapted in such a way that it is possible to turn various support mechanisms (and also restrictions) on or off.
A user study will then be conducted with this customizable tool, with the goal of finding the sweet spot between maximum restriction and maximum freedom. In order not to make the study too large, only a few useful combinations will be compared.
Task/Goal
- Familiarization with the corresponding tool
- Development and implementation of meaningful support or restriction options
- Conducting a user study (study design, creating user tasks, implementation, evaluation)
Needed skills
- Javascript/Typescript knowledge
- Experiences with React
- Interest in usability and study design
Further reading
Contact
Context
Probably everyone has had to create graphical models as part of their studies. Class diagrams, ER diagrams, state machines or sequence diagrams are popular. There are also a variety of modeling tools for this purpose, although the usability usually "takes some getting used to". Among other things, this is due to the fact that many modeling tools only allow the creation of correct models. This means, for example, that arrows must always be connected to a start and end node. However, this type of modeling often limits you or makes it more cumbersome to use.
In graphic drawing tools like Illustrator, Inkscape but also Powerpoint this restriction does not exist. However, the drawn shapes cannot be recognized as model elements and processed if necessary. One idea to counter this problem is the so-called "Relaxed Conformance Editing", which, as the name suggests, does not always require metamodel-conform graphical representations.
Problem
As part of a master's thesis, an implementation of the concepts of relaxed conformance editing has been developed. This implementation, called CouchEdit, consists of a backend that implements the basic concepts and a prototypical frontend that serves to demonstrate the functions of the backend. This backend takes arbitrary graphical elements and attempts to abstract or parse the model from them, for example by considering spatial positions relative to each other. The gathered information is used to generate suggestions such as "Make this a component of other element". Currently, these suggestions can only be accessed via the context menus of the elements. There are no visual hints that suggestions are available and there also is no visualization of which elements are referred to by a suggestion. So if there are multiple equal suggestions, the context menu has the same entry multiple times and there's no way to tell what effect each of them would have. So in summary there's a lack of proper visualizations for interacting with suggestions.
Task / Goal
- Develop visualization concepts for the interaction with relaxed conformance editing
- Implement the developed visualization concepts as a prototype or into the frontend of CouchEdit
- Evaluate the developed visualization concepts
Related Work
- Leander Nachreiner, Alexander Raschke, Michael Stegmaier, Matthias Tichy
CouchEdit: A Relaxed Conformance Editing Approach
MLE ’20: 2nd International Workshop on Modeling Language Engineering and Execution
DOI 10.1145/3417990.3421401
Contact
Self-adaptive Systems
Context
Today, software engineers are developing systems with the ability to autonomously make decisions about their structure and behaviour at runtime – so-called self-adaptive systems. Decisions that these systems make range from provisioning and releasing compute nodes in cloud or container systems, such as Googles container orchestration system Kubernetes, to selecting collision-free flight trajectories of drone swarms.
Reconfigurations are typically designed as rules containing preconditions on when to react and a execution component that defines how the system is supposed to restructure when the preconditions are met.
Problem
Most current approaches consider reconfiguration rules independently of each other. This may lead to contradictory or non-optimal behaviour, e.g., oscillations between rule applications or downstream execution that could just as well be executed earlier. Moreover the opaqueness of the decision making process within the system is a impediment during both development and operation.
To combat these limitations, we are currently developing a self-adaptive system based on the Palladio-Slingshot platform. The system aims to improve on the state of the art by providing coordination between rules and explanations of reconfiguration decisions.
Task/Goal
- Extend Palladio to allow the implementation of rule coordination
- Design interfaces for communication between system components (coordination and explanation)
- Implement basic rule analysis for rule coordination
-
Implement first and second level rule coordination
Contact
Stefan Höppner
Context
Today, software engineers are developing systems with the ability to autonomously make decisions about their structure and behaviour at runtime – so-called self-adaptive systems. Decisions that these systems make range from provisioning and releasing compute nodes in cloud or container systems, such as Googles container orchestration system Kubernetes, to selecting collision-free flight trajectories of drone swarms.
Reconfigurations are typically designed as rules containing preconditions on when to react and a execution component that defines how the system is supposed to restructure when the preconditions are met.
Problem
The opaqueness of the decision making process within the system is a impediment during both development and operation.
To combat these limitations, we are currently extending a self-adaptive system based on the Palladio-Slingshot platform. The system aims to improve on the state of the art by providing understandable explanations (through text or graphical visualisations) of reconfiguration decisions.
Task/Goal
- Extend Palladio with a component for generating post-mortem explanations
- Design suitable explanation representations
- Implement basic data extraction for explanations
-
Implement first explicit explanations based on extracted data
Contact
Stefan Höppner
Software Configuration
Feature Model Analysis
Context
A feature model of a configurable system can contain several anomalies, such as dead features, false-optional feature, or redundant constraints. There exist automated analyses for detecting these kinds of faults.
Problem
While many anomalies can be detected automatically, fixing them often requires a decision by a user on how to resolve the problem. The aim of this thesis is to investigate how and to what degree this process can be automatize.
Tasks
- Compare and discuss suitable strategies for cleaning (e.g., which redundant constraints to remove)
- Implement promising strategies in FeatureIDE
Contact
Context
Hidden features can be used to mark implementation artifacts that are not configurable by end users, but are automatically (de-)selected by the configuration editor according to the feature model. A hidden feature is called indeterminate if there is at least one configuration in which all regular features are defined but a value for the hidden feature cannot be deduced.
Problem
Indeterminate hidden features can cause a problem during configuration. Thus, these must be detected beforehand, which is a time-consuming task. The aim of the thesis is to optimize the current analysis for finding indeterminate hidden features such that it runs faster.
Tasks
- Improve the current analysis for finding indeterminate hidden features in FeatureIDE
- Evaluate the new method
Contact
Context
Given a list of configurations for a feature model (i.e., a sample), we often want to determine certain properties of it. For instance, for testing purposes, it is interesting how many potential feature interactions are covered by the sample. To this end, there exists a metric to measure t-wise interaction coverage. However, in literature the definition of this metric is often ambiguous or only given implicitly.
Problem
Due to the ambiguous definition of the coverage metric, there are multiple different variants. For example, one could include or exclude core and dead features for counting feature interaction. The same is true for abstract features. Other design decisions for the metric are whether to merge atomic sets an whether to count invalid interactions. In general, it is unclear by how much the choice of a specific metric variant impacts the results and what metric is best used in which case. This makes measuring coverage difficult and hampers comparability of new metrics and sampling tools in literature and in practice.
Tasks
- Research which variants of the metric are used in literature
- Evaluate the impact of using different variants on the same sample
Contact
Specification of Feature Models
Context
Feature-modeling tools use several different formats which induces addtional effort for researchers and practitioners. Within the MODEVAR initiative, researchers around the globe develop the Universal Variability Language (UVL) which is a textual format for specifying feature models.
Problem
UVL should be readable and editable in text format. To make editing more of a breeze, edit support, such as syntax highlighting is required. One prevalent way for language support are Language Server Protocols (LSPs) which can be more easily embedded in modern IDEs.
Tasks
- Implement Language Server Protocol (LSP)
- Embed in your favorite IDE
- Allow syntax highlighting
- Classify errors and provide readable messages
Related Work
Contact
Formal Languages for Variability
Problem
When it comes to developing multi-variant software systems, software product-line engineering and analyses avoid duplicate computational effort by exploiting similarities between the different software variants. For example, in the above example the statement "lol;" is shared between the software variants including or excluding feature A. To describe and analyze variability, formal languages have been proposed that allow semantic-preserving translations to refactor expressions to increase sharing. However, the notion of having "more sharing" in a formula remains vague most of the time or different metrics have been used in the literature to measure sharing.
Task
- Literature survey on sharing metrics (for formal variability languages)
- Qualitative comparison between sharing metrics
- Definition of new metrics if necessary
- Perhaps empirical evaluation of different metrics for real systems
Related Work
Contact
Constraint-Programmierung und Constraint Handling Rules
Constraint Handling Rules
We are developing a rule-based implementation of a tool to analyse and generate graphs. It is used in the domain of mason’s marks. For thousands of years, stonemasons have been inscribing these symbolic signs on dressed stone. Geometrically, mason’s marks are line drawings. They consist of a pattern of straight lines, sometimes circles and arcs. We represent mason’s marks by connected planar graphs. Our prototype tool for analysis and generation of graphs is written in the rule-based declarative language Constraint Handling Rules. One or several of following features could be improved in this proposed work:
Goals/Tasks
- improve the vertex-centric logical graph representation, i.e. adding arcs, colors, labels,
- encode existing mason marks either by hand, from images or import from existing databases,
- recognize (sub)graphs and patterns in a graph, in particular (self-)similarities and correlations between graphs,
- perform classical algorithms on graphs like shortest paths,
- derive properties and statistics from graphs,
- generate (randomly or exhaustively) and draw graphs from given constrained subgraphs based on properties and statistics.
References
Prerequesites
- Good knowledge of Prolog and CHR
- Lecture Rule-based Programming
Contact
When algorithms are written in CHR, constraints represent both data and operations. CHR is already incremental by nature, i.e. constraints can be added at runtime. Logical retraction adds decrementality. Hence any algorithm written in CHR with justifications will become fully dynamic. Operations can be undone and data can be removed at any point in the computation without compromising the correctness of the result.
A straightforward source-to-source transformation can introduce justifications for user-defined constraints into the CHR. Then a scheme of two rules suffices to allow for logical retraction (deletion, removal) of constraints during computation. Without the need to recompute from scratch, these rules remove not only the constraint but also undo all consequences of the rule applications that involved the constraint.
Goal
Further work should investigate implementation, dynamic algorithms and application domains of CHR with justifications:
- research how logical as well as classical algorithms implemented in CHR behave when they become dynamic.
- improve the implementation, optimize and benchmark it.
- support detection and repair of inconsistencies (for error diagnosis), - support nonmonotonic logical behaviors (e.g. default logic, abduction, defeasible reasoning).
References
- Thom Frühwirth: Justifications in Constraint Handling Rules for Logical Retraction in Dynamic Algorithms.
- CHR translator
Prerequisites
- Good knowledge of Prolog and CHR
- Lecture Rule-based Programming
- Interest to learn about formal analysis methods of rule-based languages
Contact
Extend the analysis techniques and/or the associated tool from the following two research papers:
A dynamic program analysis of the non-termination problem for recursion in the Constraint Handling Rules (CHR) language: A simple program transformation for recursive rules in CHR was introduced that produces one or more adversary rules. When the rules are executed together, a non-terminating computation may arise. It was shown that any non-terminating computation of the original rule contains this witness computation.
References
- Thom Fruehwirth: A Devil's Advocate against Termination of Direct Recursion, PPDP 2015.
- Transformation Tool available (use "Devil" options).
A static program analysis of the non-termination problem for recursion in the Constraint Handling Rules (CHR) language: Theorems with so-called misbehavior conditions for potential non-termination and failure (as well as definite termination) of linear direct recursive simplification rules are given. Logical relationships between the constraints in a recursive rule play a crucial role in this kind of program analysis.
References
Prerequesites
- Lecture "Rule-Based Programming"
Contact
In distributed computation, data and processes are distributed over a network of stores and processing units. In a constraint-based programming language paradigm this means that constraints have to be annotated with spatial information defining their whereabouts. Obvious topologies are a distinction between global and local stores as well as trees. Localized constraints can also be used for so-called reified (or meta-)constraints (e.g. https://sicstus.sics.se/sicstus/docs/4.0.8/html/sicstus/Reified-Constraints.html), to store justifications and for spatial reasoning.
In Constraint Handling Rules (CHR), there is a simple source-to-source program transformation that adds local annotations to constraints.
The scope of the work includes implementation of such a transformation, their application and/or static program analysis to derive distribution patterns, i.e. to localize constraint computation while minimizing communication overhead.
References
- Edmund S. L. Lam, Iliano Cervesato and Nabeeha Fatima: CoMingle: Distributed Logic Programming for Decentralized Mobile Ensembles. In proceedings of International Conference on Distributed Computing Techniques (Coordination'15)
- A. Raffaeta and T. Frühwirth: Spatio-Temporal Annotated Constraint Logic Programming, Third International Symposium on Practical Aspects of Declarative Languages (PADL'01), Las Vegas, USA, March 2001.
- T. Frühwirth: Entailment Simplification and Constraint Constructors for User-Defined Constraints, Third Workshop on Constraint Logic Programming (WCLP 93), Marseille, France, March 1993.
Prerequesites
- Lecture "Rule-Based Programming"
Contact
Invariants (or assertions, properties, conditions) annotate program text and express static and dynamic properties of a program's execution. Invariants can be expressed as logical relations (predicates) over the program's variables. In the context of constraint-programming and Constraint Handling Rules (CHR), they amount to constraints. These can be readily added to the program to enforce the invariants. By comparing the program with and without invariants expressed as constraints using established program analysis techniques for CHR, namely confluence and program equivalence, we can check if the invariants hold in the program.
Furthermore, invariants can be strenghened and even be generated by adapting the so-called completion method (that is normally used to generate additional rules to make a CHR program confluent).
References
Prerequisites
Contact
Program slicing is a program anaylsis technique whereby one extracts properties and relationships of variables in a program by removing from the program all statements that do not effect the assignments of the variables. In the context of constraint programming and Constraint Handling Rules that deal with logical relations (predicates) this amounts to the logical operation of variable projection. This means that we remove unwanted variables that are not of interest from the program by program transformation. This transformation can be accomplished by adapting the technique of "completion". It is usually used to make a non-confluent program confluent.
References
Prerequisites
- Lecture "Rule-based Programming
Contact
Repeated recursion unfolding is a new approach that repeatedly unfolds a recursion with itself and simplifies it while keeping all unfolded rules. Each unfolding doubles the number of recursive steps covered. This reduces the number of recursive rule applications to its logarithm at the expense of introducing a logarithmic number of unfolded rules to the program. Efficiency crucially depends on the amount of simplification inside the unfolded rules. A super-linear speedup is provably possible in the best case, i.e. speedup by more than a constant factor. The optimization can lower the time complexity class of a program.
Goals
The goal is to implement this optimization scheme as a program transformation in the programming language of choice. If necessary, the scheme should be transferred from recursion to iteration constructs such as loops.
References
Prerequisite
- Excellent knowledge and programming skills in the choosen programming language.
Contact
Prolog (WAM) and then Java (JVM) popularized the concept of an abstract (or virtual) machine to implement programming languages in a systematic, portable yet efficient way. Such a machine shall be developed for CHR.
Goals
Define the abstract code instructions for CHR and to implement them.
Prerequesites
- Good knowledge of Prolog and CHR
- Lecture Rule-based Programming
- Lecture Compiler Construction (Compilerbau) (optional but very helpful)
Contact
The declarative programming language Constraint Handling Rules (CHR) is designed as a language extension to other, not necessarily declarative programming languages. There are existing implementations for Prolog, C, Java, JavaScript, and others. We want to conduct a Structured Literature Research (SLR) on existing implementations, to get an exhaustive overview over implementation techniques and patterns.
Goals
- Conduct an SLR on papers on existing CHR implementations
- Find CHR implementations without a scientific publication on public repositories on, e.g. GitHub, GitLab, ...
- Identify and document common architectures, implementation techniques and patterns
- Get an exhaustive overview over existing and historic CHR implementations
References
- T. Frühwirth: Constraint Handling Rules - What Else?
- S. Sneyers et al.: As time goes by: Constraint Handling Rules
- P. Van Weert: Efficient Lazy Evaluation of Rule-Based Programs
- P. Van Weert, P. Wuille, T. Schrijvers, B. Demoen: CHR for Imperative Host Languages
- F. Nogatz, T. Frühwirth, D. Seipel: CHR.js: A CHR Implementation in JavaScript
- Dragan Ivanović: Implementing Constraint Handling Rules as a Domain-Specific Language Embedded in Java
Prerequesites
- Interest in programming languages and (to some extend) compiler construction.
- Good knowledge of multiple programming languages and paradigms.
Contact