From 3edd9b615caf5ee37794422bdaea0e568aa0ceca Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Fri, 5 Nov 2021 12:33:32 +0100
Subject: Fix data table fonts in math mode

---
 mgr.tex | 32 ++++++++++++++++----------------
 1 file changed, 16 insertions(+), 16 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index bf59c43..14993c4 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -436,16 +436,16 @@ The construction is as follows:
 
 Additionally, for each vertex $i.q$, we store the index of the next copy of $Q$ in
 which the path of this vertex's color is broken by a lower color. Put this
-information in table \breaktable. For example, if $i.q$ is colored with color
+information in table $\breaktable$. For example, if $i.q$ is colored with color
 $c$, and when following the deterministic path from $i.q$, all encountered
 vertices are colored $c$ until $j.q'$ which is colored $c'$, then we set
 $\breaktable[i.q] = j - 1$.
 
-We can compute \breaktable\ in linear time with a single backwards pass through
+We can compute $\breaktable$ in linear time with a single backwards pass through
 the colored graph.
 
 \textbf{answering queries} Consider a query ``does $w[i, j] \in L$''. We claim that using our colored graph
-and the table \breaktable\ we can, in constant time, conclude in what state the
+and the table $\breaktable$ we can, in constant time, conclude in what state the
 automaton $A$ will end up in on the $j$th position of $w$ if it had started in
 its initial state on the $i$th position.
 
@@ -513,7 +513,7 @@ This process will again lead to a coloring with the desired properties that
 
 Now let's consider how we could answer a query ``is the branch infix from $x$
 down to $y$ in $L$?''. Here we can't proceed exactly as in the word case. We
-don't have a \breaktable\ table since a vertex in an internal node can have
+don't have a $\breaktable$ table since a vertex in an internal node can have
 arbitrarily many points below it where its color is broken by a lower one.
 Somehow we need to be able to find such a break point that is ``in the direction
 of $y$ from $x$''.
@@ -538,16 +538,16 @@ to handle such queries in constant time. The structure is heavily inspired by
 \textcite{bender2000}, where a simple algorithm for computing LCA queries is
 presented.
 
-First, we create the array \posttable\ of length $n$, which is the post-order of
+First, we create the array $\posttable$ of length $n$, which is the post-order of
 the nodes.
 
 Next, we label each node of the tree with its pre-order number. We create the
-array \prefixtable\ with the corresponding pre-order labels of the nodes in
-\posttable, i.e.  if $\posttable[i] = v$, then $\prefixtable[i]$ is $v$'s
+array $\prefixtable$ with the corresponding pre-order labels of the nodes in
+$\posttable$, i.e.  if $\posttable[i] = v$, then $\prefixtable[i]$ is $v$'s
 pre-order number.
 
-Finally, for each node of the tree, we record its index in \posttable\ in the
-array \indextable.
+Finally, for each node of the tree, we record its index in $\posttable$ in the
+array $\indextable$.
 
 \begin{observation}
     Given a node $x$ and its descendant $y$, looking at the range
@@ -563,13 +563,13 @@ array \indextable.
     \end{enumerate}
 \end{observation}
 
-The pre-order labels in \prefixtable\ are ordered according to a post-order. In
+The pre-order labels in $\prefixtable$ are ordered according to a post-order. In
 a post-order, the root of a subtree is visited directly after all its
 descendants. Since $y$ is a descendant of $x$, all values between its position
-in \prefixtable\ and $x$'s position there will also be descendants of $x$,
+in $\prefixtable$ and $x$'s position there will also be descendants of $x$,
 giving item \ref{obs-descendants}.
 
-The values in \prefixtable\ are pre-order numbers. In a pre-order, for a given
+The values in $\prefixtable$ are pre-order numbers. In a pre-order, for a given
 node $z$, the only nodes that will have lower pre-order numbers are $z$'s
 ancestors, and the children of these ancestors that are to the left of the child
 towards $z$. By starting our range at index $\indextable[y]$, we've skipped over
@@ -584,11 +584,11 @@ In our problem, we only care about ancestors of $y$ that are marked. So
 we perform one final modification of our data structure: for all non-marked
 vertices $v$, we change $\prefixtable[\indextable[v]]$ to $\infty$ (which can be
 represented by $n+1$, an integer greater than any node's pre-order label). With
-\prefixtable\ modified like this, we observe that now the minimum value of
+$\prefixtable$ modified like this, we observe that now the minimum value of
 $\prefixtable[\indextable[y], \indextable[x] - 1]$ corresponds exactly to the
 answer of our queries -- the highest marked node between $x$ and $y$.
 
-We preprocess \prefixtable\ for RMQ queries in linear time.
+We preprocess $\prefixtable$ for RMQ queries in linear time.
 
 Now when given a query $x$, $y$, we:
 
@@ -603,7 +603,7 @@ Now when given a query $x$, $y$, we:
 We can detect the siutation of there not being a marked node between $x$ and $y$
 during step \ref{hmd-algo-lookup} by checking if $\prefixtable[k]$ is smaller
 than the pre-order label of $y$. If it isn't, then all the nodes on the path
-from $x$ to $y$ were unmarked (had higher values in the modified \prefixtable\
+from $x$ to $y$ were unmarked (had higher values in the modified $\prefixtable$
 since values at indices corresponding to unmarked nodes are set to $\infty$),
 and $k$ will correspond to a marked node that's not on the path from $x$ to $y$
 (or some unmarked vertex if there were no marked vertices at all in the range we
@@ -643,7 +643,7 @@ issuing a highest marked descendant on path query on the marked tree we created
 for color $c$. The answer to this query exactly corresponds to the point where
 the path of color $c$ from our initial state merges into a lower color $c'$ on
 the path towards $y$. From here we continue as at the beginning, checking
-\componenttable\ to see if we can answer immediately, or taking another jump
+$\componenttable$ to see if we can answer immediately, or taking another jump
 down. Handling each jump takes constant time, and the number of jumps is bounded
 by $|Q|$ since we can only jump to a lower color. Thus we can answer branch
 infix regular queries in constant time.
-- 
cgit v1.2.3

