From 031bb87dd41b3210baa44edd097bd89a338ad5ab Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 11 Dec 2021 13:52:53 +0100 Subject: Expand question --- mgr.tex | 11 ++++++----- 1 file 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$. -- cgit v1.2.3