m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-10 11:47:02 -0400
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-10 11:47:02 -0400
commit14cfb03b26e469b4c2f82654a5c9528b12420066 (patch)
treef6b8be1bec7777d6fc45c014319d1029451f761c
parent3e273d96e02640fb8765d8dfa5059b2e8fad3d43 (diff)
Small rewordings
-rw-r--r--mgr.tex17
1 files changed, 10 insertions, 7 deletions
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$.