Questions tagged [tree-automata]

Tree automata work on finite or infinite trees. They generalize word automata (Finite, Buchi, Rabin, Streett, Muller, etc.).

Filter by
Sorted by
Tagged with
1
vote
1answer
54 views

Construction of a Deterministic Tree Automaton (DTA)

Let $L \subseteq \Sigma^*$ be a regular language. Let $\Sigma' = \Sigma_0 \cup \Sigma_2$ where $\Sigma_0 =\Sigma$ and $\Sigma_2=\{*\}$. We define $T_L=\{t \in t_{\Sigma'} \mid \text{The leafs from t ...
6
votes
1answer
91 views

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

In "Types and Programming Languages", Pierce gives a translation from recursive types ($\mu$ types) to types expressed as regular trees: possibly infinite trees, but with finitely many distinct ...
3
votes
0answers
19 views

Proving the (Non-)Emptiness condition for Rabin tree automata given by Pnueli and Rosner

At section 8 of the paper On the Synthesis of a Reactive Module, the authors state the following theorem: Proposition 2 (Non-Emptiness Condition) Let $A = (Q, \delta, Q_0, \Omega)$ be a tree ...
2
votes
0answers
32 views

State-of-the-art for Set Constraints?

I've recently stumbled across the field of Set constraints for program analysis, that is, solving equations of the form $exp_1 \subseteq exp_2$, where (depending on the particular variant of the ...
1
vote
0answers
36 views

How do tree automata work?

I've started with tree automata. The definition is (Leaf-to-root) Tree automaton $\mathcal M$ over (nonempty, finite) alphabet $\Sigma$ is quintuple $\mathcal M=(K,\Sigma,\delta,S,F)$ and bound $f$ ...
2
votes
1answer
34 views

Can Nondet Rabin Tree automaton be determinized?

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)