diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-10 11:47:02 -0400 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-10 11:47:02 -0400 |
commit | 14cfb03b26e469b4c2f82654a5c9528b12420066 (patch) | |
tree | f6b8be1bec7777d6fc45c014319d1029451f761c | |
parent | 3e273d96e02640fb8765d8dfa5059b2e8fad3d43 (diff) |
Small rewordings
-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$. |