Skip to main content

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
3 votes
0 answers

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 ...
xpicox's user avatar
  • 31
2 votes
0 answers

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 ...
Joey Eremondi's user avatar
1 vote
0 answers

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: ...
Taren's user avatar
  • 111
1 vote
1 answer

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? ...
BOB123's user avatar
  • 147
1 vote
0 answers

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$ ...
byk7's user avatar
  • 153
0 votes
0 answers

Is this Deterministic Unranked Root-To-Leaf Binary Tree Automata?

I believe I have a definition of deterministic root-to-leaf tree automata in the unranked binary case, and would like to check that I have this definition correct. I would also appreciate any sources ...
TomKern's user avatar
  • 103