m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-11 13:52:53 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-11 13:52:53 +0100
commit031bb87dd41b3210baa44edd097bd89a338ad5ab (patch)
tree17c23ce2e37d8860d477b5d16a95eeee2331edc8
parent521096850cc8ce92e60d861e028816b721090c8f (diff)
Expand question
-rw-r--r--mgr.tex11
1 files changed, 6 insertions, 5 deletions
diff --git a/mgr.tex b/mgr.tex
index 96f4001..a9d3121 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -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$.