Differences
This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
tree_automata [2010/05/25 15:33] vkuncak |
tree_automata [2012/05/15 15:48] vkuncak |
||
---|---|---|---|
Line 37: | Line 37: | ||
Example: | Example: | ||
- | * bottom up tree automaton checking the parity of the number of nodes in the tree | + | * bottom up tree automaton accepting trees with an even number of nodes in the tree, in alphabet with constant 'a', binary function 'f'. |
+ | * bottom up tree automaton accepting expressions with complement, union, intersection; accepting only expressions that are monotonic in each variable | ||
Non-deterministic top-down tree automaton: reverse a bottom-up tree automaton | Non-deterministic top-down tree automaton: reverse a bottom-up tree automaton | ||
Deterministic top-down tree automaton: more restrictive. Is there deterministic automaton to check the parity of the number of nodes? | Deterministic top-down tree automaton: more restrictive. Is there deterministic automaton to check the parity of the number of nodes? | ||
- | |||
- | |||
- | |||
===== Closure Properties of Tree Automata ====== | ===== Closure Properties of Tree Automata ====== | ||
Line 60: | Line 58: | ||
Projection. | Projection. | ||
+ | |||
===== Weak Monadic Logic of Two Successors (WS2S) ===== | ===== Weak Monadic Logic of Two Successors (WS2S) ===== | ||
Line 81: | Line 80: | ||
where $succ0$ takes a tree node and finds its left child: | where $succ0$ takes a tree node and finds its left child: | ||
\[ | \[ | ||
- | \alpha(succ) = \{ (\{w\},\{w0\}) \mid w \in \Sigma^* \} | + | \alpha(succ0) = \{ (\{w\},\{w0\}) \mid w \in \Sigma^* \} |
\] | \] | ||
and where $succ1$ takes a tree node and finds its right child: | and where $succ1$ takes a tree node and finds its right child: | ||
\[ | \[ | ||
- | \alpha(succ) = \{ (\{w\},\{w1\}) \mid w \in \Sigma^* \} | + | \alpha(succ1) = \{ (\{w\},\{w1\}) \mid w \in \Sigma^* \} |
\] | \] | ||