m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-17 22:26:07 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-17 22:26:07 +0100
commitb6b15d9b554ba2ae931c106cd1dd3288d5fca4a5 (patch)
tree6498d49ef7931e884a78c2fc2e3f52e2c16c2104
parent72e25ef2de37bd15646331dcde3179480f931bdf (diff)
Small fixes
-rw-r--r--mgr.tex10
1 files 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