From efe68b7702eee84432158c8065b107046f79354c Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 6 Aug 2021 14:29:57 -0400 Subject: Define the branch infix query problem --- mgr.tex | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) 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} -- cgit v1.2.3