Add extra copy of Q in word case

1 files changed, 16 insertions, 13 deletions

diff --git a/mgr.tex b/mgr.tex
index 4188c4a..ee1ce7b 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -391,20 +391,23 @@ automaton we ``don't care'' about the exponential cost of determinizing it.
     j]$ belong to $L$?
 }
 
-This problem has a very elegant \qpoptimal{} solution, as presented by
-\textcite{bojanczyk}. We present the full construction as we will be
-generalizing its internals for the tree case in Chapter \ref{branchinfix}.
+Let $n$ be the length of $w$. This problem has a very elegant \qpoptimal{}
+solution, as presented by \textcite{bojanczyk}. We present the full construction
+as we will be generalizing its internals for the tree case in Chapter
+\ref{branchinfix}.
 
-\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$.
+\textbf{preprocessing} We begin by creating a graph whose vertices are $n+1$
+copies of the set of states of $A$, $Q$.  More precisely, we will be working
+with a graph whose vertex set is $\{0, 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
 copies of $Q$. For example, suppose the $i$th letter of $w$ is $a$. If $A$ in
 state $q$, reading $a$, would move to state $q'$, then there will be an edge
-from $i.q$ to $(i+1).q'$.
+from $(i-1).q$ to $i.q'$. We can think of this construction as first drawing
+copies of $Q$ around each letter of $w$, then replacing each letter by the edges
+induced by it in $A$'s transition function.
 
 Note that by determinism, each vertex has exactly one outgoing edge (except for
 vertices in the last copy of $Q$ which have no outgoing edges at all).
@@ -476,11 +479,11 @@ position.
 First, look at vertex $i.q_0$, which is the vertex of $A$'s initial state in the
 $i$th copy of $Q$ and note its color $c$. Now we want to answer the following
 question: if we follow the edges of the graph until the $j$th copy of $Q$, what
-color will we end in? First, look at $k := \breaktable[i.q_0]$. If $k \geq j$,
-then we know that in the $j$th copy of $Q$, the path we're interested in still
-has color $c$. Find the unique vertex $j.q$ in this copy of $Q$ that's colored
-with $c$. $q$ is the state we will end up in, so if it is an accepting state
-answer YES, if not, answer NO.
+color will we end in? First, look at $k := \breaktable[(i-1).q_0]$. If $k \geq
+j$, then we know that in the $j$th copy of $Q$, the path we're interested in
+still has color $c$. Find the unique vertex $j.q$ in this copy of $Q$ that's
+colored with $c$. $q$ is the state we will end up in, so if it is an accepting
+state answer YES, if not, answer NO.
 
 If $k < j$, then jump to the $k$th copy of $Q$ and consider the vertex $k.q$,
 the unique vertex here colored $c$. From $k.q$, follow its single outgoing edge