LARA

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

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^* \}
 \] \]