# Questions tagged [tree-automata]

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

6 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
27 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 ...
• 31
38 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 ...
• 29.8k
1 vote
26 views

### Extending minimal top-down tree automata

I'm trying to find an algorithm to update minimal top-down tree automata/hypergraphs. Regular tree grammars can be seen as definitions for recursive data structures: ...
• 111
1 vote
135 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? ...
• 147
1 vote
102 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$ ...
• 153