State Space Reductions for Alternating B
Carsten Fritz, Thomas Wilke · 2002
Quotienting by simulation equivalences is a well-established technique for reducing the size of nondeterministic Buchi automata. We adapt this technique to alternating Buchi automata. To this end we suggest two new quotients, namely minimax and semi-elective quotients, prove that they preserve the recognized languages, and show that computing them is not more difficult than computing quotients for nondeterministic Buchi automata. We explain the merits of of our quotienting procedures with respect to converting alternating Buchi automata into nondeterministic ones.