You are here: Home Finished [B.Sc. Thesis] … [B.Sc. Thesis] Minimization of …

[B.Sc. Thesis] Minimization of Finite Automata

We implement several minimization algorithms for finite automata in our framework and compare time and memory consumption. Additionally, we want to solve the question whether parallelization can improve the existing approaches.
Course type B. Sc. Project, B. Sc. Thesis, M.Sc. Lab
Instructors Christian Schilling
Credits Depending on course type

Background

We use nested word automata in some tools for program verification. To keep things tractable, we apply a minimization algorithm to those automata, which is based on a standard minimization algorithm for finite automata. However, our implementation is time-consuming.

We want to adapt more minimization algorithms to our setting. In order to guide our choice, we would like to compare several minimization algorithms and their implementations.

An interesting (yet undiscovered) question we want to solve is how to combine minimization algorithms to run in parallel and exchange information.

Task

  1. As a first introduction to our automata framework (and to be able to test and evaluate the algorithms later on) you implement a random generator for finite automata (in Java).
  2. Depending on the course type you implement several minimization algorithms in our framework. For this you read the relevant paper, transfer the algorithm to our framework and implement it.
  3. The algorithms are adapted in a way that they can be run in parallel.
  4. You evaluate the implementations using the random generator.

Follow-Up Work

There is an option of follow-up work. In another project you could adapt your favorite algorithm (or several of them if the parallel approach was successful) to our real-world scenario (nested word automata).