You are here: Home Student Projects and … Finished [M.Sc. Laboratory] Reducing the …

[M.Sc. Laboratory] Reducing the Size of Büchi Automata

Course type Master Laboratory
Instructors Matthias Heizmann
Credits Depending on course type
Course Catalog
Note

For a regular language L there is a minimal deterministic finite automaton which recognizes L. Given a deterministic finite automaton A we can always compute this minimal deterministic automaton that recognizes the language of A.

For ω-regular language there is no analogous notion of a minimal Büchi automaton. However for some Büchi automata we can reduce the size of the automaton. We will develop an algorithm for this task.

 

Input: Büchi Automaton A
Output: Büchi Automaton A' such that L(A)=L(A') and the size of A' is not greater than the size of A.

 


Result:

We implemented both approaches in our automata library.