m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 14:04:49 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-10-07 14:04:49 +0200
commit3509ea1cea043944b676bc33f41ed9bb1867f7cf (patch)
treeac3b7b44cdae6d2b380134cfa5bf0cd429042775
parent2dfc18dada547f7ea250257c4a167e5d09fde4ba (diff)
Use x.q notation
-rw-r--r--mgr.tex19
1 files changed, 11 insertions, 8 deletions
diff --git a/mgr.tex b/mgr.tex
index 092a614..65e596a 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -362,12 +362,15 @@ The query problem we will solve is:
}
We begin with a similar construction as in the word case, i.e. we replace each
-vertex of the tree with a copy of the states of $A$, $Q$. Again, each letter
-defines a function $a : Q \to Q$, and these functions induce edges in our
-``fattened'' tree: if $A$ in state $q$, reading letter $a$ goes to $q'$, then a
-copy of $Q$ corresponding to an internal node of $T$ will have edges going to
-$q'$ in all of the copies of $Q$ corresponding to the children of this node in
-$T$.
+vertex of the tree with a copy of the states of $A$. Call the set of $T$'s
+vertices, $V$, then our new graph has vertex set $V \times Q$, and we can refer
+to a specific vertex as $x.q$ for $x \in V$, $q \in Q$.
+
+Again, each letter $a \in \Sigma$ defines a function $a : Q \to Q$, and these
+functions induce edges in our ``fattened'' tree: consider a vertex $x$ of $T$,
+labeled with letter $a$ and having children $y$ and $z$. If $A$ in state $q$,
+reading letter $a$ goes to $q'$, then there will be edges from $x.q$ to $y.q'$
+and $z.q'$.
We also color all vertices with $1, \ldots, |Q|$ in this graph, analogously to
how we did so in the word case: begin by coloring an arbitrary vertex in the
@@ -380,8 +383,8 @@ This process will again lead to a coloring with the desired properties that
\begin{enumerate}
\item every copy of $Q$ has one vertex of each of the $|Q|$ colors;
- \item when a vertex of color $i$ has an edge to a vertex of color $j$ in a
- child copy of $Q$, then $i \geq j$.
+ \item when a vertex of color $c$ has an edge to a vertex of color $c'$ in a
+ child copy of $Q$, then $c \geq c'$.
\end{enumerate}
Now let's consider how we could answer a query ``is the branch infix from $x$