From 3509ea1cea043944b676bc33f41ed9bb1867f7cf Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 7 Oct 2021 14:04:49 +0200 Subject: Use x.q notation --- mgr.tex | 19 +++++++++++-------- 1 file 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$ -- cgit v1.2.3