From 2dfc18dada547f7ea250257c4a167e5d09fde4ba Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Thu, 7 Oct 2021 13:53:20 +0200
Subject: Use i.q notation

---
 mgr.tex | 38 ++++++++++++++++++++++----------------
 1 file changed, 22 insertions(+), 16 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 0d536d3..092a614 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -320,22 +320,28 @@ $\breaktable[i.q] = j - 1$.
 We can compute \breaktable\ in linear time with a single backwards pass through
 the colored graph.
 
-To handle the query ``does $w[i, j] \in L$'', we look at vertex $v$, 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[v]$. 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$. Look at the state in this copy
-of $Q$ that's colored with $c$, if it's an accepting state answer YES, if not,
-answer NO.
-
-If $k < j$, then jump to the $k$th copy of $Q$ and take the edge from the vertex
-colored $c$ here to the next copy of $Q$. The vertex $v'$ we end up in will be
-colored with color $c' < c$. Continue as we did before, by looking at $k' :=
-\breaktable[v']$, comparing it to $j$, and either halting if $k' \geq j$, or
-jumping again otherwise. Because with each jump we move to a color strictly
-smaller than before, the number of jumps is bounded by the number of colors,
-$|Q|$. Thus the query is answered in time constant with respect to $|w|$.
+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.
+
+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.
+
+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
+to $(k+1).q'$, which will be colored with color $c' < c$. Continue as we did
+before, by looking at $k' := \breaktable[(k+1).q']$, comparing it to $j$, and either
+halting if $k' \geq j$, or jumping again otherwise. Because with each jump we
+move to a color strictly smaller than before, the number of jumps is bounded by
+the number of colors, $|Q|$. Thus the query is answered in time constant with
+respect to $|w|$.
 
 \chapter{Branch Infix Regular Queries}\label{branchinfix}
 
-- 
cgit v1.2.3