From c1885675cedfee307890c7a01ecc78cab5c0cb34 Mon Sep 17 00:00:00 2001
From: Marcin Chrzanowski <mc370754@students.mimuw.edu.pl>
Date: Sat, 7 Aug 2021 13:58:37 -0400
Subject: Define queryproblem macro

---
 mgr.tex | 29 +++++++++++++++++------------
 1 file changed, 17 insertions(+), 12 deletions(-)

(limited to 'mgr.tex')

diff --git a/mgr.tex b/mgr.tex
index 70776b8..e343a66 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -2,6 +2,8 @@
 % dodaj opcję [en] dla wersji angielskiej (mogą być obie: [licencjacka,en])
 \documentclass[en]{pracamgr}
 
+\usepackage{definitions}
+
 % Dane magistranta:
 \autor{Marcin Chrzanowski}{370754}
 
@@ -33,9 +35,6 @@
 
 \keywords{MSO, query answering, tree automata, RMQ}
 
-% Tu jest dobre miejsce na Twoje własne makra i~środowiska:
-\newtheorem{definition}{Definition}[chapter]
-
 \begin{document}
 \maketitle
 
@@ -142,16 +141,20 @@ 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$?
 
-
+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
 
 \section{Highest Black Descendant on Path}
 
 We can now reduce the problem to the following:
 
-\emph{Given}: a tree $T$ with distinguished black vertices.
-
-\emph{Queries}: given a vertex $x$, its descendant $y$, find the node $z$ that
-is the highest black node on the path between $x$ and $y$.
+\queryproblem{Highest Marked Descendant on Path}{%
+    a tree $T$ with distinguished black vertices
+}{%
+    given a vertex $x$, its descendant $y$, find the node $z$ that
+    is the highest black node on the path between $x$ and $y$
+}
 
 We will build an index structure, constructible in linear time, that allows us
 to handle such queries in constant time. The structure is heavily inspired by
@@ -161,10 +164,12 @@ Berkman and Vishkin for computing LCA queries.
 First, let's define an auxillary problem we will use, that of Range Minimum
 Queries (RMQ):
 
-\emph{Given}: an array $A$ of integers.
-
-\emph{Queries}: given indices $i$ and $j$, return the index of the smallest
-element in the subarray $A[i, j]$.
+\queryproblem{Range Minimum Query}{%
+    an array $A$ of integers.
+}{%
+    given indices $i$ and $j$, return the index of the smallest
+    element in the subarray $A[i, j]$.
+}
 
 Fact: RMQ queries can be answered in constant time after linear preprocessing of
 the input array.
-- 
cgit v1.2.3