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
---
definitions.sty | 12 ++++++++++++
mgr.tex | 29 +++++++++++++++++------------
2 files changed, 29 insertions(+), 12 deletions(-)
create mode 100644 definitions.sty
diff --git a/definitions.sty b/definitions.sty
new file mode 100644
index 0000000..f6d2e94
--- /dev/null
+++ b/definitions.sty
@@ -0,0 +1,12 @@
+\newtheorem{definition}{Definition}[chapter]
+
+% #1: Name of query problem
+% #2: The structure to preprocess
+% #3: Queries to handle
+\newcommand{\queryproblem}[3]{
+ \textsc{#1}
+
+ \textbf{Given:} #2
+
+ \textbf{Queries:} #3
+}
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