diff options
Diffstat (limited to 'mgr.tex')
| -rw-r--r-- | mgr.tex | 10 |
1 files changed, 5 insertions, 5 deletions
@@ -802,7 +802,7 @@ This concludes the proof of the lemma, and Theorem \begin{theorem}\label{relabel-regular-queries-theorem} Problem \ref{relabel-regular-queries} can be solved in time - \qptime{$O(n)$}{$O(m \log m)$} + \qptime{$O(n)$}{$O(m \log m)$}. \end{theorem} The rest of this chapter is dedicated to proving Theorem @@ -1099,9 +1099,9 @@ this formally, consider the alphabet $\Sigma' := Q \times \Sigma \times Q \times \{ \leftsymbol, \rightsymbol \}$. A word over this alphabet can be used to represent a subtree with a hole. A subtree with hole as described above would be represented by word $\alpha_0 \alpha_1 \ldots \alpha_p$ with each $\alpha_i$ -being a quadruple from $\Sigma'$, $\langle p_i, a_i, q_i, d_i \rangle$ (with -$p_i, q_i \in Q$, $a_i \in \Sigma$, $d_i$ either $\leftsymbol$ or -$\rightsymbol$) where: +being a quadruple $\langle p_i, a_i, q_i, d_i \rangle \in \Sigma'$ (with $p_i, +q_i \in Q$, $a_i \in \Sigma$, $d_i$ either $\leftsymbol$ or $\rightsymbol$) +where: \begin{itemize} \item $a_i$ is the original label of $u_i$. @@ -1134,7 +1134,7 @@ by the previously read letter, what state we arrived in at it and whether it was the current vertex's left or right child. The automaton works as follows: \begin{enumerate} - \item In the initial state $\mathsf{initial}$, read $\alph_0 = \langle p_0, + \item In the initial state $\mathsf{initial}$, read $\alpha_0 = \langle p_0, a_0, q_0, d_0 \rangle$, set the state to $\langle q, d_0 \rangle$. \item Now when reading letter $\alpha_i = \langle p_i, a_i, q_i, d_i \rangle$ in state $\langle r, d \rangle$, if $d$ if $\leftsymbol$, use |