m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-14 16:45:59 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-14 16:45:59 +0200
commit19c3c46fe457534fe991d1c7ce29e6ecdb44370c (patch)
tree88d9c4e3fcabb218eba3f2d8f2b7b462cc234bc2
parent350d4fb6f6368aa083d0670f712e538ced126e3c (diff)
Add headings
-rw-r--r--mgr.tex10
1 files changed, 5 insertions, 5 deletions
diff --git a/mgr.tex b/mgr.tex
index 5ccc072..a855f5a 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -390,10 +390,10 @@ This problem has a very elegant \qpoptimal{} solution. We present the full
construction as we will be generalizing its internals for the tree case in
Chapter \ref{branchinfix}.
-We begin by replacing each letter of $w$ with the set of states of $A$, $Q$.
-More precisely, we will be working with a graph whose vertex set is $\{1,
-\ldots, |w|\} \times Q$. We will refer to a vertex in the $i$th copy of $Q$
-labeled with state $q$ as $i.q$.
+\textbf{preprocessing} We begin by replacing each letter of $w$ with a copy of the set of states of
+$A$, $Q$. More precisely, we will be working with a graph whose vertex set is
+$\{1, \ldots, |w|\} \times Q$. We will refer to a vertex in the $i$th copy of
+$Q$ labeled with state $q$ as $i.q$.
Since $A$ is deterministic, each letter $a \in \Sigma$ can be seen as a function
$a : Q \to Q$, and we draw these functions as directed edges between successive
@@ -444,7 +444,7 @@ $\breaktable[i.q] = j - 1$.
We can compute \breaktable\ in linear time with a single backwards pass through
the colored graph.
-Consider a query ``does $w[i, j] \in L$''. We claim that using our 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
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.