diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-10-07 14:04:49 +0200 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-10-07 14:04:49 +0200 |
commit | 3509ea1cea043944b676bc33f41ed9bb1867f7cf (patch) | |
tree | ac3b7b44cdae6d2b380134cfa5bf0cd429042775 | |
parent | 2dfc18dada547f7ea250257c4a167e5d09fde4ba (diff) |
Use x.q notation
-rw-r--r-- | mgr.tex | 19 |
1 files changed, 11 insertions, 8 deletions
@@ -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$ |