From 2b993ec2297422f1be7695f417e4bdb35622e4d3 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Sat, 7 Aug 2021 14:34:48 -0400
Subject: Define various query problems

---
 mgr.tex | 43 ++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 42 insertions(+), 1 deletion(-)

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
-- 
cgit v1.2.3