From 33bc657bc838a56e0c3a884520c493a91e72bf57 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Sat, 7 Aug 2021 16:14:47 -0400
Subject: Begin defining tree automata
---
mgr.tex | 33 ++++++++++++++++++++++++++++++++-
1 file changed, 32 insertions(+), 1 deletion(-)
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
--
cgit v1.2.3