From 33bc657bc838a56e0c3a884520c493a91e72bf57 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski 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