From 19c3c46fe457534fe991d1c7ce29e6ecdb44370c Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 14 Oct 2021 16:45:59 +0200 Subject: Add headings --- mgr.tex | 10 +++++----- 1 file 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. -- cgit v1.2.3