Skip to main content
7 votes

Can all regular tree types be expressed as $\mu$ types?

You can reduce mutual recursion to a single recursion, see Bekic's Theorem, see e.g. Section 10.1 of Winskel's (1), where Bekic is worked out for programs rather than types. Note however that the ...
Martin Berger's user avatar
3 votes

Can Nondet Rabin Tree automaton be determinized?

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$. ...
Shaull's user avatar
  • 17.3k
2 votes

Resources on Tree Automata Regular Expressions

Here is a master's thesis and an arXiv paper on the topic, which contains some examples.
codeR's user avatar
  • 1,750

Only top scored, non community-wiki answers of a minimum length are eligible