In other words, are they equally powerful?

(for word automata the answer is "yes"; this question is about tree automata).

(i am talking about tree automata that work on $in$finite trees)


1 Answer 1


The answer is no, nondeterministic Rabin automata are more expressive than deterministic ones.

As an example, consider the language of $\{a,b\}$-labeled binary trees that contain at least one $b$.

It's easy to construct a two-state Büchi tree automaton for this language (and hence a Rabin automaton), but there is no deterministic equivalent.

You can look at Lemma 6.1 here, for a start.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.