Büchi Automata and Their Degrees of Nondeterminism and Ambiguity
Frank Nießner · Journal of automata, languages and combinatorics · 2004
Nondeterminism and ambiguity in abstract machines can be considered as consumable resources. This was first done by Goldstine, Kintala and Wotschke for finite automata. We extend their method to finite automata which accept words of infinite length, so-called regular $\omega$-automata. We classify the automata with respect to the amount of nondeterminism and ambiguity that is needed to accept a corresponding regular $\omega$-language and present examples for each of the classes. It is a well-known fact that the deterministic regular $\omega$-languages are a proper subset of the nondeterministic ones. Hence we specify the amount of nondeterminism and ambiguity that is necessary to accept a nondeterministic regular $\omega$-language. Finally, we show for all possible amounts of nondeterminism that there is no interrelation between nondeterminism and ambiguity.