Questions tagged [tree-automata]
Tree automata work on finite or infinite trees. They generalize word automata (Finite, Buchi, Rabin, Streett, Muller, etc.).
8
questions
1
vote
0
answers
20
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
1
answer
120
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
1
answer
79
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 ...
- 113
7
votes
1
answer
157
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 ...
- 29.7k
3
votes
0
answers
25
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
2
votes
0
answers
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.7k
1
vote
0
answers
87
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
2
votes
1
answer
38
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)
- 1,055