diff options
| -rw-r--r-- | mgr.tex | 11 |
1 files changed, 6 insertions, 5 deletions
@@ -945,11 +945,12 @@ are in $W'$, thus showing $W'$ is LCA closed and finishing the proof of Lemma \section{Computing root states of parts} Let's now describe how we will use LCA paritions to solve the relabel questions -problem. Our approach is the following: given a question $v_1 \mapsto a_1, -\ldots, v_m \mapsto a_m$, let $W = \{ v_1, \ldots, v_m \}$. Consider the -partition of $T$ with respect to $W$. We will show how to compute $A$'s state in -the root of each part of the partition, after the tree had been relabeled. Per -our definition of the partition, we have three types of parts to consider: +problem. Our approach is the following: given the question ``is $T$ accepted by +$A$ after relabeling according to $v_1 \mapsto a_1, \ldots, v_m \mapsto a_m$?'', +let $W = \{ v_1, \ldots, v_m \}$. Consider the partition of $T$ with respect to +$W$. We will show how to compute $A$'s state in the root of each part of the +partition, after the tree had been relabeled. Per our definition of the +partition, we have three types of parts to consider: \begin{enumerate} \item A subtree rooted at vertex $v$. |