From 3509ea1cea043944b676bc33f41ed9bb1867f7cf Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Thu, 7 Oct 2021 14:04:49 +0200
Subject: Use x.q notation

---
 mgr.tex | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)

(limited to 'mgr.tex')

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

