From c4965bcb7d623e0b105469e31e48c4c354e07bff Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Fri, 13 Aug 2021 07:27:45 -0400
Subject: Write branch infix regular query algorithm

---
 mgr.tex | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 66 insertions(+), 3 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 7e0d443..919a9b8 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -328,9 +328,38 @@ The query problem we will solve is:
     the path from $x$ to $y$ belong to $L$?
 }
 
-We begin with similar path coloring as in the word case, i.e. we replace each
-vertex of the tree with a copy of the states of $A$, $Q$. Each labeled node
-defines
+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$.
+
+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
+root with $1$, then follow edges downwards, coloring all visited vertices with
+$1$. Then begin the same process with the next color, restarting with a
+different vertex in a given copy of $Q$ if we run into an already colored
+vertex.
+
+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$.
+\end{enumerate}
+
+Now let's consider how we could answer a query ``is the branch infix from $x$
+down to $y$ in $L$?''. Here we can't proceed exactly as in the word case. We
+don't have a $BREAK$ table since a vertex in an internal node can have
+arbitrarily many points below it where its color is broken by a lower one.
+Somehow we need to be able to find such a break point that is ``in the direction
+of $y$ from $x$''.
+
+In the next section we formulate this question formally and solve it as a
+subproblem.
 
 \section{Highest Marked Descendant on Path}
 
@@ -390,6 +419,40 @@ Now when given a query $x$, $y$, we:
         answer to our query.
 \end{enumerate}
 
+\section{Solving branch infix regular queries}
+
+With the above problem solved, we are ready to finish our solution to the branch
+infix regular query problem. Recall that we have replaced the input tree $T$'s
+vertices with copies of $Q$, then connected and colored them in the same way as
+in the word case. We additionally remember in each vertex a unique identifier of
+the connected component of vertices of the same color that it's in (call this
+data $COMPONENT[v]$).
+
+For each color $c$, we will preprocess the above graph for queries that answer
+the question ``if we start in a vertex $v$ colored with $c$, which is the first
+copy of $Q$ on the path towards the copy of $Q$ that contains $y$?'' by creating
+a copy of $T$ in which we mark the vertices where an edge from a $c$ colored
+vertex points to a vertex with a lower color. This tree we preprocess for the
+queries from the previous section.
+
+Now query answering can proceed similar to the word case. Given a query ``does
+the word on vertices from $x$ down to $y$ belong to $L$?'' find the copy of $Q$
+corresponding to $x$ and consider the color $c$ corresponding to the initial
+state here. If in the copy of $Q$ corresponding to $y$, the vertex of color $c$
+has the same $COMPONENT$ information as the initial state we were considering,
+we can immediately answer whether or not $A$ will accept the word on this path
+based on whether this state is accepting.
+
+Otherwise, we need to jump down to a lower copy of $Q$. We do this by issuing a
+highest marked descendant on path query on the marked tree we created for color
+$c$. The answer to this query exactly corresponds to the point where the path of
+color $c$ from our initial state merges into a lower color $c'$ on the path
+towards $y$. From here we continue as at the beginning, checking $COMPONENT$ to
+see if we can answer immediately, or taking another jump down. Handling each
+jump takes constant time, and the number of jumps is bounded $|Q|$ since we can
+only jump to a lower color. Thus we can answer branch infix regular queries in
+constant time.
+
 \chapter{Relabel Regular Queries on Trees}
 h
 
-- 
cgit v1.2.3