« May 2017 »
May
MoTuWeThFrSaSu
1234567
891011121314
15161718192021
22232425262728
293031
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