m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-11-05 12:33:32 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-11-05 12:33:32 +0100
commit3edd9b615caf5ee37794422bdaea0e568aa0ceca (patch)
treeb573dc34f5d1ebac5f48b0868253c651c5f9641d
parent99c36deb1ec967327190af8dc412e8362e49dbd3 (diff)
Fix data table fonts in math mode
-rw-r--r--definitions.sty2
-rw-r--r--mgr.tex32
2 files changed, 17 insertions, 17 deletions
diff --git a/definitions.sty b/definitions.sty
index ea91bb0..f3731ea 100644
--- a/definitions.sty
+++ b/definitions.sty
@@ -28,7 +28,7 @@
\newcommand{\definedterm}[1]{\emph{#1}}
-\newcommand{\data}[1]{\textsf{#1}}
+\newcommand{\data}[1]{\mathsf{#1}}
\newcommand{\infixtable}{\data{in}}
\newcommand{\posttable}{\data{post}}
\newcommand{\prefixtable}{\data{pre}}
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.