« April 2017 »
April
MoTuWeThFrSaSu
12
3456789
10111213141516
17181920212223
24252627282930
Uni-Logo
You are here: Home Teaching Student Projects and Thesis Topics Finished [M.Sc. Laboratory] Reducing the Size of Büchi Automata
Document Actions

[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.

Personal tools