Deciding Nondeterministic Hierarchy of Deterministic Tree Automata
Damian Niwiński, Igor Walukiewicz · Electronic Notes in Theoretical Computer Science · 2005
We show an algorithm which, for a given deterministic parity automaton on infinite trees, computes the minimal Mostowski (or Rabin) index of a nondeterministic automaton recognizing the same language. This extends a previous result of Urbański on deciding if a given deterministic Rabin automaton is equivalent to a nondeterministic Büchi automaton. The algorithm runs in the time of verifying the non-emptiness of nondeterministic parity automata.