diff options
| -rw-r--r-- | mgr.tex | 10 |
1 files changed, 5 insertions, 5 deletions
@@ -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. |