m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-06 14:29:57 -0400
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-06 14:29:57 -0400
commitefe68b7702eee84432158c8065b107046f79354c (patch)
treef50d451a4af5600d215f92a5b351c57fbf313b87
parent112232de666efd87c5e7dbf05efa277564cea204 (diff)
Define the branch infix query problem
-rw-r--r--mgr.tex13
1 files changed, 12 insertions, 1 deletions
diff --git a/mgr.tex b/mgr.tex
index cf7bb8b..9ac68b0 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -133,7 +133,18 @@ The construction is as follows:
Additionally, in each vertex, we store the index of the next copy of $Q$ in
which the path of this vertex's color is broken by a lower color.
-\section{Least Common Ancestor via Range Minimum Query}
+\section{Generalizing to trees}
+
+We will now generalize the above construction from regular infix queries on a
+word, to ones on a tree. The exact problem we're solving is
+
+\emph{Given}: a tree $T$ with labels from alphabet $\Sigma$, a deterministic
+finite automaton $A$.
+
+\emph{Queries}: given a vertex $x$ and its descendant $y$, is the word given by
+labels on the path from $x$ to $y$ accepted by $A$?
+
+
\section{Highest Black Descendant on Path}