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
1 answer
60 views

Algorithm to determine if a top-down non deterministic tree automata accepts some tree?

Given a non-deterministic top-down tree-automata. is there an algorithm, that can determine if there exists any tree that accepted by this automaton? if so, what is the most efficient algorithm known? ...
user avatar
  • 137
1 vote
1 answer
70 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 ...
user avatar
  • 113
7 votes
1 answer
144 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 ...
user avatar
  • 29.1k
3 votes
0 answers
22 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 ...
user avatar
  • 31
2 votes
0 answers
36 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 ...
user avatar
  • 29.1k
1 vote
0 answers
62 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$ ...
user avatar
  • 143
2 votes
1 answer
37 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)
user avatar
  • 1,016