From 14cfb03b26e469b4c2f82654a5c9528b12420066 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Tue, 10 Aug 2021 11:47:02 -0400 Subject: Small rewordings --- mgr.tex | 17 ++++++++++------- 1 file changed, 10 insertions(+), 7 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index 362cc45..7e0d443 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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$. -- cgit v1.2.3