diff options
| -rw-r--r-- | mgr.tex | 17 |
1 files changed, 10 insertions, 7 deletions
@@ -253,11 +253,12 @@ Chapter \ref{branchinfix}. We begin by replacing each letter of $w$ with the set of states of $A$, $Q$. -Each letter $a$ of $w$ defines an injective function on $Q$, and we draw these -functions as directed edges between successive copies of $Q$. For example, if -$A$ in state $q$, reading $a$, would move to state $q'$, then, for any copy of -$Q$ corresponding to an instance of $a$ in the original word, there will be an -edge from $q$ there to $q'$ in the successive copy of $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, if $A$ in state $q$, reading $a$, would move to +state $q'$, then, for any copy of $Q$ corresponding to an instance of $a$ in the +original word, there will be an edge from $q$ there to $q'$ in the successive +copy of $Q$. Now we will color the vertices of the graph we just constructed with the colors $1, 2, \ldots, |Q|$ in such a way that @@ -313,8 +314,10 @@ query is answered in time constant with respect to $|w|$. Before solving our main problem, that of MSO queries on trees, we generalize word infix regular queries (section \ref{wordinfix}) to trees. This will be a -vital step in the MSO queries algorithm, but is an interesting result on its own -so it deserves its own chapter. +vital step in the MSO queries algorithm, but is an interesting result on its +own. + +The query problem we will solve is: \queryproblem[% regular language $L$ over alphabet $\Sigma$. |