Begin defining tree automata

1 files changed, 32 insertions, 1 deletions

diff --git a/mgr.tex b/mgr.tex
index 1310a16..85ed507 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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