diff options
| -rw-r--r-- | mgr.tex | 11 |
1 files changed, 6 insertions, 5 deletions
@@ -202,13 +202,14 @@ The rest of our work is organized in the following way: \section{Definitions} \subsection{Trees} -We work with finite trees whose vertices are labeled with letters from a finite -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, +We work with finite rooted trees whose vertices are labeled with letters from a +finite 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. A tree $T$ can then also be seen as an acyclic -undirected graph with vertex set $V(T)$ and edge set $E(T)$. +undirected graph with vertex set $V(T)$ and edge set $E(T)$, with a +distinguished root vertex $r \in V(T)$. -We use the standard notions of root, child, sibling, ancestor, descendant, etc. +We use the standard notions of leaf, 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 |