diff options
| -rw-r--r-- | mgr.tex | 52 |
1 files changed, 26 insertions, 26 deletions
@@ -1032,27 +1032,27 @@ answered with a branch infix regular question. \subsection{Computing the root state of a subtree with a hole} -Consider the subtree of $x$ with hole $y$. It can be divided into the following +Consider the subtree of $v$ with hole $w$. It can be divided into the following components: \begin{itemize} - \item $y$'s subtree - \item A path from $y$ up to $x$, notate it as $x_0 = y, x_1, \ldots, x_p = - x$. - \item For each $i$ from 1 to $p$, the subtree of $x_i$'s child that doesn't - lie on the path from $y$ to $x$. Let $x_i'$ be the child of $x_i$ that - doesn't lie on the $y$ to $x$ path. + \item $w$'s subtree + \item A path from $w$ up to $v$, notate it as $u_0 = w, u_1, \ldots, u_p = + v$. + \item For each $i$ from 1 to $p$, the subtree of $u_i$'s child that doesn't + lie on the path from $y$ to $x$. Let $u_i'$ be the child of $u_i$ that + doesn't lie on the $w$ to $v$ path. \end{itemize} -With our bottom-up computation, we've already computed the new state in $y$. -There have been no relabelings in the subtrees of the $x_i'$'s, so we can get +With our bottom-up computation, we've already computed the new state in $w$. +There have been no relabelings in the subtrees of the $u_i'$'s, so we can get their states from the precomputed run of $A$ on the original tree. Now consider -how, using all this information, we could easily compute $x$'s new state. +how, using all this information, we could easily compute $v$'s new state. -To compute the state in $x_1$, all we need is $x_1$'s label and the states of -$x_0$ and $x_1'$ -- $x_1$'s children. This is all information we already have. -So going up the path from $y$ to $x$, we can compute each $x_i$'s new state -from its label and the states of $x_{i-1}$ and $x_i'$. The computation as just +To compute the state in $u_1$, all we need is $u_1$'s label and the states of +$u_0$ and $u_1'$ -- $u_1$'s children. This is all information we already have. +So going up the path from $w$ to $y$, we can compute each $u_i$'s new state +from its label and the states of $u_{i-1}$ and $u_i'$. The computation as just described would take time linear in $p$, the length of the path, but the computation is simple enough that it could be performed by a finite state word automaton, allowing us to use our result from Chapter \ref{branchinfix}. To show @@ -1064,16 +1064,16 @@ from $\Sigma'$, $\langle p_i, b_i, q_i, d_i \rangle$ (with $p_i, q_i \in Q$, $b_i \in \Sigma$, $d_i$ either $\leftsymbol$ or $\rightsymbol$) where: \begin{itemize} - \item $b_i$ is the original label of $x_i$. - \item $p_i$ and $q_i$ are the states of $x_i$'s children in the precomputed + \item $b_i$ is the original label of $u_i$. + \item $p_i$ and $q_i$ are the states of $u_i$'s children in the precomputed run of $A$ over $T$. - \item $d_i$ encodes the information of whether $x_i$ is the left or right + \item $d_i$ encodes the information of whether $u_i$ is the left or right child of its parent. \end{itemize} Note that this is slightly more information than we previously mentioned: in our description of the computation above we only cared about the state of the child -not on the $y$ to $x$ path. The information about the other child is redundant +not on the $w$ to $v$ path. The information about the other child is redundant when considering just one subtree with hole and can be ignored when doing computation on that particular subtree with hole. But we will keep information about both children so that we can handle questions about any subtree with hole. @@ -1112,18 +1112,18 @@ Our algorithm for branch infix regular questions dealt with top-down questions (i.e. the word we ask about runs from a higher vertex down to its descendant). Regular languages are reversible, so we can preprocess $T$ for branch infix regular questions for each language $L_{q, q'}^R$ (where $\cdot^R$ denotes the -reversed language). A question about whether the word on the path from $x$ down -to $y$ belongs to $L_{q, q'}^R$ is the same as asking if the word from $y$ up to -$x$ belongs to $L_{q,q'}$. Note that the number of languages we need to +reversed language). A question about whether the word on the path from $v$ down +to $w$ belongs to $L_{q, q'}^R$ is the same as asking if the word from $w$ up to +$v$ belongs to $L_{q,q'}$. Note that the number of languages we need to preprocess for is constant in the size of the tree -- it only depends on the size of the automaton. -Given the subtree of $x$ with hole $y$, once we've computed $y$'s new state $q$, -to compute $x$'s new state, take $x'$ -- $x$'s child in the direction of $y$, -find $q' \in Q$ such that the path from $x'$ to $y$ belongs to $L_{q, q'}^R$ +Given the subtree of $v$ with hole $w$, once we've computed $w$'s new state $q$, +to compute $v$'s new state, take $v'$ -- $v$'s child in the direction of $w$, +find $q' \in Q$ such that the path from $v'$ to $w$ belongs to $L_{q, q'}^R$ (using branch infix regular questions; since $A$ is deterministic, there will be -exactly one such $q'$). Now from $q'$, the state of $x$'s other child, and $x$'s -new label, use $A$'s transition function to compute $x$'s new state. +exactly one such $q'$). Now from $q'$, the state of $v$'s other child, and $v$'s +new label, use $A$'s transition function to compute $v$'s new state. Since $T$'s root is the root of one of the parts of our LCA partition, in the end we will know whether or not $A$ accepts $T$ after relabeling. Handling each |