« November 2017 »
November
MoTuWeThFrSaSu
12345
6789101112
13141516171819
20212223242526
27282930
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