Topics for bachelor and master thesis as well as projects

Topics for bachelor and master theses as well as projects come from the areas of software engineering and programming languages. The concrete topics for theses are oriented towards our research areas.  Basics are taught in the corresponding courses of the institute.

The following list offers a selection of topics and subject areas. More detailed information can be obtained from the respective contact persons. In addition, we are open to your own suggestions for topics.

(Legend - B: Bachelor Thesis, M: Master Thesis, P: Project)

Algorithm Detecion

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our envisioned solution consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms. Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system.

Problem
In order to describe multiple algorithms with a DSL and create a library of such descriptions one needs to identify the "essence" of multiple algorithms first. The "essence" of an algorithm are the essential features with which the algorithm can be identified uniquely. These features include the code itself, but also control-flow and data-flow descriptions if possible. Possible ways to extract those features are to:

  • compare implementations and look for commonalities and differences
  • consult text books, publications and other official specifications
  • examine pseudo code

Tasks

  • Select algorithms which would be useful to detect
  • Gather open source implementations
  • Extract the "essence" of the algorithms
  • Describe the "essence" and why it is suitable to detect the algorithm
  • Annotate the open source implementations

Related Work

  • Literature about algorithms: 
    • T.H. Cormen, C.E. Leiserson, R.L. Rivest: Introduction to Algorithms. MIT Press, 1990.
    • U. Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.
    • In Search of an Understandable Consensus Algorithm by Diego Ongaro and John Ousterhout
  • Related literature about representing abstract concepts of source code:
    • Chapters 1-3 from "Automatic Algorithm Recognition and Replacement A New Approach to Program Optimization" by Robert Metzger and Zhaofang Wen
    • Using Attributed Flow Graph Parsing to Recognize Cliches in Programs, Linda Mary Wills
    • A memory-based approach to recognizing programming plans, A. Quilici

Contact

Denis Neumüller

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our envisioned solution consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms. Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system.

Problem
In order to further underpin the necessity/usefulness of our algorithm detection approach we want to investigate how students would otherwise search for algorithms implemented in a code base with a user study. Additionally, the study will help us to gain insights into which expectations/requirements users have towards algorithm detection in order to be useful for them.

Tasks

  • Design a user study
    • Specify research questions and a procedure
    • Select algorithms
  • Prepare the user study
    • Gather code bases implementing the algorithms and "control" code bases
    • Select tools provided to the users (eg. the IDE and a specialized search tool)
  • Trial-run the user study
  • Conduct the user study
  • Analyze the results (encode, transcribe, statistics ...)

Possible Research Questions

  • How do developers search for algorithms contained in a code base?
    • Which search strategies are employed?
    • How long did users search till ... (they found one | they found x algorithms | they stopped looking.)
  • Demographic Question:
    • Which tool are/have been used in the past?
    • Have participants searched for algorithms in the past?
    • Which kind of assistance would users find helpful?

Related Work

  • Literature on case studies:
    • Yin, R. K. (2009). Case study research: Design and methods
    • Case Study Research in Software Engineering - Guidelines and Examples. Wiley 2012, ISBN 978-1-118-10435-4
    • Experimentation in Software Engineering, https://doi.org/10.1007/978-3-642-29044-2
  • Literature on code search:

Contact

Denis Neumüller

M: User study: code search (Neumüller, Tichy)

Context
We are convinced that automatically detecting algorithm implementations in a code base can be helpful to gain knowledge about, which concerns are present in the code base, how they are solved and which components are involved. This knowledge can then support the tasks of software comprehension, software architecture recovery and software maintenance. Our envisioned solution consists of a Domain Specific Language (DSL) designed to describe key features of an algorithm, a search algorithm to find these features and a set of “ready to use” descriptions for common algorithms. Examples for algorithms which could be interesting to detect and some of the insights their detection provides:

  • Quicksort -> The application sorts data structure x.
  • A* -> The application does path search.
  • Raft (Consensus Algorithm) -> The application is a distributed, fault-tolerant system.

Problem
Currently, we are working on an abstract syntax tree based prototype to investigate our ideas. Besides ASTs, program dependence graphs (PDG) and system dependence graphs (SDG) are also widely used for analyzing source code. They represent control flow and data flow explicitly and could therefore be more suitable for the recognition of algorithms. The goal of this topic is to implement an SDG-based prototype. Given the description of an algorithm, the prototype should be able to search for the description in the code base.

Tasks

  • Compare existing frameworks/libraries for analyzing source code with SDGs
  • Use an existing library to start building the prototype
  • Select and implement search features
  • Describe a few algorithms and search for them with the prototype
  • Evaluate the prototype
  • Compare the SDG-prototype with the AST based prototype?

Related Work

Contact

Denis Neumüller

P/B/M: SDG-based prototype for algorithm detection (Neumüller, Tichy)

Domain Specific Languages

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

Chico Sundermann, Thomas Thüm

Graphs

Context

Representing information in a graph like manner has become the norm for many application domains. Be it “social graphs”, as used by Facebook and other social media platforms, or “knowledge graphs” used to connect words and meanings for search engines and question-answer systems like Amazon Alexa, Siri or WolphramAlpha, or the standard path graphs used for routeplaning.
As a result, querying and manipulating graph structures is an ever present task in many software systems. Many domain specific languages (DSLs) have thus been developed to tackle this task such as GraphQL, Gremlin or Cipher in neo4j.
Domain specific languages have the advantage of having a concise syntax tailored to the task at hand.

Problem

Current approaches are either stand-alone tools or integrate poorly into the general purpose programming languages (GPLs) used to develop complete software systems. This hampers development where data from graphs needs to be integrated into the control flow of the developed system. There is therefore a need to bridge the gap between graph querying DSLs and GPLs that allows seamless integration of the domain expressiveness of DSLs into the host programming languages. Much like LINQ in C# does this for SQL.

Task/Goal

  • Design 1-3 approaches for representing graph queries in a 3rd gen GPL
  • Implement integration approaches in prototypes
  • Evaluate usability and performance of the prototypes against each other

Contact

Stefan Höppner

Analysis Methods for Complex Model Transformations

Context

Model-driven software engineering (MDSE) is centered around the transformation of models through complex transformation chains that are constructed by composing basic transformation steps. These basic steps apply a transformation rule on an input model to create an output model. We focus on the Henshin framework for declarative model transformations.

Problem

Defects in either the transformation rule or the input model can cause a basic transformation step to not be applicable at all or produce wrong output. At a higher level, defects in the structure of a transformation chain might schedule the application of basic steps incorrectly, thus leading to applicability issues or unexpected behavior. Due to the declarative nature of transformation steps and nondeterminism in pattern matching or scheduling of steps, these bugs are often difficult to find and fix.

One possible approach to assist developers with understanding and debugging complex transformations is to present a visualization of the control flow through the transformation and offer features to edit this control flow and interact with it.

Task / Goal

  • Development of a control flow visualization for Henshin transformations.
  • Integration in the Henshin tool (based on Eclipse Rich Client Platform).
  • Evaluation of the implementation with regard to
    • performance: what are the costs in time and memory space?
    • usability: how does the approach compare to exisiting features concerning identification and fixing of defects in transformations?

Contact

Florian Ege

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
Due to the underlying operation-based versioning technique, to recreate the state of a distinct model version, all edit operations until that version have to be reapplied. In the current prototype – depending on the size of the edit history – this can take up to several seconds which is not appropriate for users. To handle this problem and reduce the loading time, we require a model state cache. Since we utilize a directed acyclic graph (DAG) and disable edit operations to solve edit conflicts, this is not trivial.

Tasks

  • Develop an efficient caching algorithm for a DAG.
    • Your algorithm should ensure loading of any version within predefined time.
    • But: it should consume as less memory as possible.
  • Conduct performance benchmarks.

Related Work

Contact

Jakob Pietron

P/BA: Efficient caching for operation-based versioning (Pietron, Tichy)

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

Contact

Jakob Pietron

P/B/M: Reducing of visually interfering edit operations (Pietron, Tichy)

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

Contact

Jakob Pietron

M: Query language for model edit histories (Pietron, Tichy)

Quadcopter Lab

Context
rosslt ist eine C++ Bibliothek + Integration in ROS (Robot Operating System), die das Setzen und Verändern von Werten über Komponentengrenzen ermöglicht. In einer einfachen Robotikanwendung könnten z.B. in einer Komponente Wegpunkte erzeugt werden, in einer anderen Komponente eine Trajektorie durch diese Wegpunkte geplant werden und in einer dritten Komponente diese Trajektorien visualisiert werden. Jeder berechnete Wert hängt dabei von den ursprünglichen Wegpunkten ab. Ziel ist es, diese berechneten Werte veränderbar zu machen, indem die Berechnungen umgekehrt und auf die ursprünglichen Daten zurückzuführen. Dazu werden die Datenflüsse zur Laufzeit durch die rosslt Bibliothek getrackt und bei Bedarf invertiert.

Problem
Das Location-Tracking von ROS-Messages erlaubt es, den Ursprung (Node, Parameter) einzelner Nachrichten festzustellen. Das Ziel der Abschlussarbeit/des Projekts ist, dies graphisch aufzubereiten und interaktiv zu visualisieren. Eine solche Oberfläche sollte es erlauben zur Laufzeit ROS-Topics zu abbonieren, Nachrichten anzuzeigen und zu verändern. Dabei sollte die Source-Location der Nachricht genutzt werden um im Ursprungsnode so Änderungen vorzunehmen (z.B. Parameter setzen), dass sich die Änderung auch auf die folgenden Nachrichten entsprechend auswirkt. Zusätzlich kann der Ursprung und die Historie jedes Wertes in einer Message visualisiert werden um Datenflüsse und Berechnungen interaktiv zu debuggen.

Contact
Thomas Witte

Context
rosslt ist eine C++ Bibliothek + Integration in ROS (Robot Operating System), die das Setzen und Verändern von Werten über Komponentengrenzen ermöglicht. In einer einfachen Robotikanwendung könnten z.B. in einer Komponente Wegpunkte erzeugt werden, in einer anderen Komponente eine Trajektorie durch diese Wegpunkte geplant werden und in einer dritten Komponente diese Trajektorien visualisiert werden. Jeder berechnete Wert hängt dabei von den ursprünglichen Wegpunkten ab. Ziel ist es, diese berechneten Werte veränderbar zu machen, indem die Berechnungen umgekehrt und auf die ursprünglichen Daten zurückzuführen. Dazu werden die Datenflüsse zur Laufzeit durch die rosslt Bibliothek getrackt und bei Bedarf invertiert.

Problem
Das Location-Tracking von ROS-Messages ist derzeit unoptimiert und nur in einer einzigen Variante (Tracking einer einzelnen Quelle pro Wert, direkte Auflösung von Alternativen, Speicherung der History in der Message, …) implementiert. Ziel der Arbeit soll einerseits die Implementierung und Optimierung weiterer Varianten, sowie die Evaluation und der Vergleich des Einflusses dieser Alternativen/Optimierungen auf die Performance sein. Hierzu könnten eigene, synthetische Benchmarks entwickelt werden, bestehende Anwendungen angepasst und instrumentiert werden, oder die Datenstukturen und Algorithmen auf ihre theoretische Komplexität untersucht werden.

Contact
Thomas Witte

Context
Selbstadaptive Systeme sind Systeme, die ihr Verhalten zur Laufzeit an geänderte Umgebungsbedingungen anpassen können. Safety und Security sind wichtige Eigenschaften selbstadaptiver Systeme, die durch die zunehmende Vernetzung und Komplexität immer stärker gemeinsam betrachtet und analysiert werden müssen.

Problem
Unser Quadcoptersystem im Quadcopterlabor soll als Demonstrator und zur Evaluation eines neu entwickelten Frameworks zur Safety und Securityanalyse dienen. Zunächst soll als Teil der Arbeit systematisch analysiert werden, welche Fähigkeiten und Adaptionen innerhalb des Labors sinnvoll umsetzbar sind. In weiteren Phasen soll ein möglichst realistisches Szenario entwickelt werden, das Safety und Security Ereignisse verknüpft und durch Adaption des Systems mitigiert. Dieses Szenario soll schließlich implementiert und analysiert werden.

Contact
Thomas Witte

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

Alexander Raschke

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

Michael Stegmaier

Safety and Security

Context

Each software uses different componentes such as libraries, protocols, communication channels, drivers, etc., all of which may be targets for security attacks. In order to be able to scan existing databases for vulnerabilities, it is necessary to know which components in which versions are used by a running software on a concrete system. At least Linux-based systems offer the possibility to query parts of this information with different tools.

Problem

In this thesis an extensible system is to be developed, which merges the outputs of different Linux tools and thus provides as comprehensive a picture as possible of the components used in a software on a concrete system. This data will then serve as a basis for security analyses.
To ensure that the interrelationships used in this to be developed tool are well documented on the one hand and remain as easily extensible as possible on the other, a hierarchical model has to be established that represents high-level interrelationships but also describes at the lowest level which information is derived from which outputs.

Task/Goal

  • Compilation of relevant information of a system and how to obtain it
  • Creation of a hierarchical model
  • Development of a configurable tool to analyze the interrelationships of an application based on a refinement of the model

Needed skills

  • deeper knowledge of Linux
  • programming skills related to operating system interaction and text parsing
  • nice to have: ROS knowledge

Contact

Alexander Raschke

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-Simulizar 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

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

Sebastian Krieter

Analyzing Product Lines with #SAT

Context
A #SAT solver computes the number of satisfying assignments of a propositional formula. This number is required for a variety of problems in different domains. For example, #SAT solvers enable a high number of analyses on feature models. However, #SAT is a computationally complex task and widely regarded as harder than SAT.

Problem
Due to the hardness of #SAT, state-of-the-art solvers often do not scale for complex formulas. One solution considered are approximate #SAT solvers which estimate the number of satisfying assignments. The required runtime of such solvers is heavily dependent on parameters used for the approximation. The goal is to identify effective parameters to achieve a strong trade-off between runtime and result quality.

Tasks

  • Research approximate #SAT solvers
  • Analyze parameters allowed by the solvers
  • Find heuristic(s) for parametrization based on feature models and the propositional formula representing it
  • Evaluate heuristic(s)

Related Work

Contact

Chico Sundermann, Thomas Thüm

Context
A #SAT solver computes the number of satisfying assignments of a propositional formula. This number is required for a variety of problems in different domains. For example, #SAT solvers enable a high number of analyses on feature models. However, #SAT is a computationally complex task and widely regarded as harder than SAT.

Problem
#SAT solvers perform differently depending on the given feature model. There seems to be no one-solver-fits-them-all solution. Thus, it is beneficial to switch between solvers according to the input which have been applied to regular SAT with large sucess. However, it is not trivial to determine which solver is the most efficient given a feature model.

Tasks

  • Gather promising #SAT solvers
  • Analyze structural properties of feature models
  • Develop heuristic(s) to select solvers depending on structure
  • Empirically evaluate heuristic(s)

Related Work

Contact

Chico Sundermann, Thomas Thüm

 

Context
A #SAT solver computes the number of satisfying assignments of a propositional formula. This number is required for a variety of problems in different domains. For example, #SAT solvers enable a high number of analyses on feature models. However, #SAT is a computationally complex task and widely regarded as harder than SAT.

Problem
For many feature-model analyses dependent on counting, a high number of #SAT invocations is required. For instance, some analyses require the count for every single feature (up-to ten thousands in the industry). With current #SAT solvers, a computation is reqiured for each of those features. Reusing information between such invocations may reduce the required runtime.

Tasks

  • Develop concept for variational #SAT
  • Possible options:
  1. Develop your own tooling
  2. Adapt existing solver
  • Empirically evaluate variational #SAT solver

Related Work

Contact

Chico Sundermann, Thomas Thüm

 

Knowledge Compilation

Context
Propositional formulas are prevalent in a variety of computer science domains.  Such formulas are typically evaluated with SAT solvers which commonly operate on conjuctive normal form (CNF) due to its beneficial properties.

Problem
A large variety of translation techniques to CNF have been considered in the literature which typically result in semantically equivalent but different CNFs. It has been shown that the performance of SAT/#SAT solvers are heavily dependent on the resulting CNF. The goal of this work is to compare several CNF translation techniques. Furthermore, the runtime of SAT and #SAT solvers when given the different CNFs shall be examined.

Tasks

  • Research on CNF translation techniques
  • Implement CNF translation techniques
  • Implement comparison benchmark for CNFs

Related Work

Contact

Chico Sundermann, Thomas Thüm

Context
A d-DNNF is a normal form for propositional formulas that allows faster queries for certain analyses. For example, a d-DNNF representing a feature model allows to compute the number of valid configurations within polynomial time. However, compiling any formula and, thus, a feature model to d-DNNF is computationally expensive.

Problem
Feature models are typically evolving over time. After a change, it may be beneficial to adapt the existing d-DNNF instead of compiling the entire formula again. Your task is to incrementally adapt an existing d-DNNF according to changes in the feature model.

Tasks

  • Handle changes performed on CNF incrementally
  • Handle changes performed on feature model incrementally
  • Implement prototype
  • Empirically evaluate the benefits


Related Work

Contact

Chico Sundermann, Thomas Thüm

Context
A d-DNNF is a target format of knowledge compilation that can be used, inter alia, for linear-time counting.

Problem
While the compilation to d-DNNF is well researched, algorithms for exploitation of d-DNNFs are mostly limited to counting. Therefore, it is currently unknown which feature-model analyses are generally tractable (i.e., have a polynomial time complexity) for d-DNNFs.

Tasks

  • Collect existing feature-model analyses
  • Analyze applicability of analyses on d-DNNFs
  • Develop algorithms that exploit the structure of d-DNNFs
  • Implement algorithms
  • Empirically evaluate your implementation

Related Work

Contact

Chico Sundermann, Thomas Thüm

ddueruem-web is a RESTful (web)service for ddueruem, which acts as an interface to (legacy) BDD libraries. FeatureIDE is an IDE for model-driven software development that is principially developed by our working group.
The goal of this project is the integration of the two tools via the RESTful API of ddueruem-web. Work on this project may also be conducted as part of a Bachelor's thesis.

Individual points of emphasis and own ideas are highly appreciated.

The project can be conducted as a 8, 12, or 16 LP project,.

Contact
Tobias Heß, Thomas Thüm

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

Thom Frühwirth, Sascha Rechenberger

P/B/M: Graph Tool for Mason Marks (Rechenberger, Frühwirth)

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

Prerequisites

  • Good knowledge of Prolog and CHR
  • Lecture Rule-based Programming
  • Interest to learn about formal analysis methods of rule-based languages

Contact

Thom Frühwirth, Sascha Rechenberger

P/B/M: Justifications in CHR for Logical Retraction in Dynamic Algorithms (Rechenberger, Frühwirth)

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


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

Thom Frühwirth, Sascha Rechenberger

B/M: Non-Termination Analysis of Recursive Rules (Rechenberger, Frühwirth)

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

Prerequesites

  • Lecture "Rule-Based Programming"

Contact

Thom Frühwirth, Sascha Rechenberger

P/B/M: Localized Constraint Stores (Rechenberger, Frühwirth)

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

Thom Frühwirth, Sascha Rechenberger

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

Thom Frühwirth, Sascha Rechenberger

B/M: Program Slicing by Confluence and Completion (Rechenberger, Frühwirth)

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

Thom Frühwirth, Sascha Rechenberger

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

Thom Frühwirth, Sascha Rechenberger

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. Since there still plenty of languages for which there is no implementation, or at least no maintained one, and since the problems that can be tackled using CHR are plentiful (think of any problem including the simplification of constraints, or derivation of new from existing information), we want to work on spreading CHR to those languages as well, by designing and (prototypically) implementing runtime environments (RTEs) for CHR in those languages still lacking a CHR implementation.

Goals

  • Design a runtime environment for CHR, which is able to deal with the specific features of the language of your choice. This may includes implementing logical variables, if they are not already a feature of the language.
  • Design translations schemes from CHR to your language of choice
  • Implement a prototype of your RTE, and test it extensively with (manually) translated CHR programs, as well as unit tests.
  • (additionally for Masters theses/projects) Implement an embedding of CHR into your language of choice. This may be a compiler, a macro system, or an embedded domain specific language (EDSL); whatever your language offers in this regard.

References

Prerequesites

  • Interest in programming language design and (to some extend) compiler construction.
  • Good programming skills and knowledge of the inner workings of CHR and the programming language of your choice.

Contact

Sascha Rechenberger

Data-Oriented Programming (DOP) is a programming paradigm that evolved from Object-Oriented Programming (OOP) and Functional Programming (FP). The main principles of DOP are

  • the separation of code and data (in contrast to OOP), i.e, functions are not rigidly linked to a user-defined data-type
  • data is always immutable
  • the use of generic data structures, instead of user-defined data-types. E.g., instead of defining a data-type (class) with different fields, dictionaries (heterogenous maps) are used

Those principles make dynamically typed languages like LISP-dialects or JavaScript-derivates ideal for this paradigm, and in fact, a major representative of data-oriented languages is the fairly modern LISP-dialect Clojure. On the other hand, it is almost impossible to keep true to all of those principles in most statically typed languages like Java or Haskell (mostly because of the use of generic data structures).

This comes with a price, though: since we use dynamic-typing, we can never guarantee at compile time, that a dictionary, for example, has the field a function needs to work with it. Languages like TypeScript or PureScript solve this, by beeing able to give partial type annotations for JSON-like objects. Such an approach can be interpreted as a constraint-based type system, where a data-object has to satisfy constraints of the kind "has field X of type T" where X is a key of some sort, and T a data-type.

Since Prolog also offers dictionaries, is a dynamically typed language, and offers a powerful macro-system, it is a perfect playground to experiment with such an approach. Thus, we want to implement an annotation system for Prolog predicates, that gives the programmer the option to add type-annotations to a predicate, that are checked at compile time, and then, if successfully checked, removed.

Goals

  • Design a contraint-based type-system for DOP in Prolog
  • Implement a type-checker for said type-system using Prolog and Constraint Handling Rules
  • Desing user-friendly type-annotations for this type-system

Prerequesites

  • Lecture Rule-Based Programming (strongly recommended)

References

Contact

Sascha Rechenberger

Software Evolution