From 56633c5d2149f9706b6ebcb2949544cf1a2d9b86 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Wed, 7 Dec 2022 19:25:46 +0100 Subject: Fix indexing --- mgr.tex | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/mgr.tex b/mgr.tex index 07c3c6e..787cd91 100644 --- a/mgr.tex +++ b/mgr.tex @@ -507,14 +507,14 @@ 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-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. +First, look at vertex $(i-1).q_0$, which is the vertex of $A$'s initial state in +the $(i-1)$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-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 -- cgit v1.2.3