diff options
| -rw-r--r-- | mgr.tex | 33 |
1 files changed, 32 insertions, 1 deletions
@@ -100,8 +100,39 @@ alphabet. More formally, given a finite alphabet $\Sigma$, for each $a \in \Sigma$, $a$ is a tree, and if $t_1, \ldots, t_k$ are trees, then $a(t_1, \ldots, t_k)$ is also a tree. +We use the standard notions of root, child, sibling, ancestor, descendant, etc. + +Binary trees are trees where each node has either no children (the node is a +leaf), or exactly two children (which, based on their order, can be called the +left and the right child). + \subsection{Tree automata} -c + +Consider the case of binary trees labeled with $\Sigma$. A +\definedterm{deterministic, bottom-up tree automaton} (further called just a +\definedterm{tree automaton}) consists of + +\begin{itemize} + \item A finite set of \definedterm{states} $Q$. + \item A set of \definedterm{accepting states} $F \subseteq Q$. + \item A bottom-up \definedterm{transition function} $\delta : Q \times + \Sigma \times Q \to Q$. + \item An \definedterm{initializatoin function} $\iota : \Sigma \to Q$. +\end{itemize} + +A \definedterm{run} of tree automaton $A$ over tree $T$ is a relabeling of $T$ +with the elements of $Q$ such that + +\begin{itemize} + \item Each leaf with label $a \in \Sigma$ is relabeled with $\iota(a)$. + \item If an inner node $v$ has label $a \in \Sigma$, its left child got + relabeled to $p \in Q$, and its right child got relabeled to $q \in Q$, + then $v$ gets relabeled with $\delta(p, a, q)$. +\end{itemize} + +A run is \definedterm{accepting} if $T$'s root gets relabeled to an accepting +state, that is a state $q \in F$. + \subsection{Monadic Second Order (MSO) Logic} % def of MSO |