From d93a6bf0e2e3d0cae2208ca710466697dfd1344b Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 11 Dec 2021 15:31:11 +0100 Subject: Add extra copy of Q in word case --- mgr.tex | 29 ++++++++++++++++------------- 1 file 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 -- cgit v1.2.3