| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 9655958 | Electronic Notes in Theoretical Computer Science | 2005 | 14 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Damian NiwiÅski, Igor Walukiewicz,