State Space Reduction For Parity Automata

Exact minimization of ω-automata is a difficult problem and heuristic algorithms are a subject of current research. We propose several new approaches to reduce the state space of deterministic parity automata. These are based on extracting information from structures within the automaton, such as strongly connected components, coloring of the states, and equivalence classes of given relations, to determine states that can safely be merged. We also establish a framework to generalize the notion of quotient automata and uniformly describe such algorithms. The description of these procedures consists of a theoretical analysis as well as data collected from experiments.

Authors

• Christof Löding
• Andreas Tollkötter

Keywords

• automata
• \omega-automata
• parity
• minimization
• state space reduction
• deterministic
• simulation relations