m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-07 14:34:48 -0400
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-08-07 14:34:48 -0400
commit2b993ec2297422f1be7695f417e4bdb35622e4d3 (patch)
treee140a23c446974dc4765a537f8d9f22bbba74bdd
parentce335794a175e28e7de356d41dfd20bf2b88766e (diff)
Define various query problems
-rw-r--r--mgr.tex43
1 files changed, 42 insertions, 1 deletions
diff --git a/mgr.tex b/mgr.tex
index e343a66..c78dfca 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -56,6 +56,19 @@
\chapter{Introduction}
% \addcontentsline{toc}{chapter}{Introduction}
+\queryproblem[%
+ an MSO formula $\varphi(\vec{X})$ over trees with $k$ free
+ second-order variables.
+]{%
+ MSO Query Answering on Trees
+}{%
+ a tree $T$.
+}{%
+ given a $k$-tuple of subsets of $T$'s vertices $\vec{W}
+ \in \mathcal{P}(V(T))^{k}$, is $\vec{W}$ a satisfying assignment to
+ $\vec{X}$? In other words, does $T \models \varphi(\vec{W})$?
+}
+
\chapter{Preliminaries}\label{r:pojecia}
% \begin{quote}
@@ -75,14 +88,42 @@ c
d
\section{Known algorithms we will use}
\subsection{Least Common Ancestor}
-e
+
+\queryproblem{%
+ Least Common Ancestor (LCA)
+}{%
+ a tree $T$.
+}{%
+ given vertices $x$ and $y$, find the vertex $z$ that's an ancestor of both
+ $x$ and $y$, and is their lowest (i.e. furthest from the root) common
+ ancestor.
+}
+
\subsection{Range Minimum Query}
f
\chapter{Branch Infix Regular Queries}\label{r:branchinfix}
+\queryproblem[%
+ regular language $L$ over alphabet $\Sigma$.
+]{Branch Infix Regular Queries}{%
+ a $\Sigma$-labeled tree $T$.
+}{%
+ given a vertex $x$ and its descendant $y$, does the word given by labels on
+ the path from $x$ to $y$ belong to $L$?
+}
+
\section{Word infix regular queries}
+\queryproblem[%
+ regular language $L$ over alphabet $\Sigma$.
+]{Word Infix Regular Queries}{%
+ a word $w \in \Sigma^*$.
+}{%
+ given indices $i$ and $j$ with $1 \leq i < j \leq |w|$, does the infix $w[i,
+ j]$ belong to $L$?
+}
+
There is a simple and well-known data structure that, given a fixed automaton
$A$, preprocesses an input word $w$ in time $O(n)$, and afterwards is able to
answer in time $O(1)$ questions of the form ``Is the infix $w[i, j]$ accepted by