Differences

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

--- tree_automata [2010/05/25 15:32]
vkuncak
+++ tree_automata [2010/05/27 18:10]
vkuncak
@@ Line 42: / Line 42: @@
 Deterministic top-down tree automaton: more restrictive. Is there deterministic automaton to check the parity of the number of nodes?
@@ Line 56: / Line 57: @@
   * intersection
-Comparison to context-free grammars: closure under intersection and complement
+Comparison to context-free grammars: closure under intersection and complement. Parser trees are regular, their yield is not.
 Projection.
 ===== Weak Monadic Logic of Two Successors (WS2S) =====
@@ Line 80: / Line 82: @@
 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:
 \[
-   \alpha(succ) = \{ (\{w\},\{w1\}) \mid w \in \Sigma^* \}
+   \alpha(succ1) = \{ (\{w\},\{w1\}) \mid w \in \Sigma^* \}
 \]
 The meaning of formulas is then given by standard [[sav08:First-order logic semantics]].
 ===== Deciding WS2S =====
 A construction is similar to one for WS1S and is possible thanks to closure properties of finite automata.
+Examples:
+  * subset
+  * successor
 ===== Verification of Trees =====