From b6b15d9b554ba2ae931c106cd1dd3288d5fca4a5 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 17 Dec 2021 22:26:07 +0100 Subject: Small fixes --- mgr.tex | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/mgr.tex b/mgr.tex index 56ad569..3be81ed 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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 -- cgit v1.2.3