Skip to main content
7 votes
Accepted

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
Accepted

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
Accepted

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