diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-07 13:58:37 -0400 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-08-07 13:58:37 -0400 |
commit | c1885675cedfee307890c7a01ecc78cab5c0cb34 (patch) | |
tree | 10bf790540be992d75756404aaa4d61e9a767656 | |
parent | 127c81cb5209241fc96c9d676bab6fd6e60186f6 (diff) |
Define queryproblem macro
-rw-r--r-- | definitions.sty | 12 | ||||
-rw-r--r-- | mgr.tex | 29 |
2 files changed, 29 insertions, 12 deletions
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 +} @@ -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. |