diff options
| author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-17 22:26:07 +0100 | 
|---|---|---|
| committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-12-17 22:26:07 +0100 | 
| commit | b6b15d9b554ba2ae931c106cd1dd3288d5fca4a5 (patch) | |
| tree | 6498d49ef7931e884a78c2fc2e3f52e2c16c2104 | |
| parent | 72e25ef2de37bd15646331dcde3179480f931bdf (diff) | |
Small fixes
| -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 |