Initial commit

2 files changed, 552 insertions, 0 deletions

diff --git a/mgr.tex b/mgr.tex
new file mode 100644
index 0000000..86217d9
--- /dev/null
+++ b/mgr.tex
@@ -0,0 +1,175 @@
+% dodaj opcję [licencjacka] dla pracy licencjackiej
+% dodaj opcję [en] dla wersji angielskiej (mogą być obie: [licencjacka,en])
+\documentclass[en]{pracamgr}
+
+% Dane magistranta:
+\autor{Marcin Chrzanowski}{370754}
+
+\title{MSO Query Answering on Trees}
+\titlepl{Odpowiadanie na zapytania MSO na drzewach}
+\kierunek{Computer Science}
+
+% Praca wykonana pod kierunkiem:
+% (podać tytuł/stopień imię i nazwisko opiekuna
+% Instytut
+% ew. Wydział ew. Uczelnia (jeżeli nie MIM UW))
+\opiekun{dr hab. Szymon Toruńczyk\\
+  Institute of Informatics\\
+  }
+
+% miesiąc i~rok:
+\date{August 2021}
+
+%Podać dziedzinę wg klasyfikacji Socrates-Erasmus:
+\dziedzina{
+%11.0 Matematyka, Informatyka:\\
+%11.1 Matematyka\\
+% 11.2 Statystyka\\
+11.3 Informatyka\\
+%11.4 Sztuczna inteligencja\\
+%11.5 Nauki aktuarialne\\
+%11.9 Inne nauki matematyczne i informatyczne
+}
+
+%Klasyfikacja tematyczna wedlug AMS (matematyka) lub ACM (informatyka)
+\klasyfikacja{% TODO
+  D. Software\\
+  D.127. Blabalgorithms\\
+  D.127.6. Numerical blabalysis}
+
+% Słowa kluczowe:
+\keywords{MSO, query answering, trees, finite state automata, tree automata}
+
+% Tu jest dobre miejsce na Twoje własne makra i~środowiska:
+\newtheorem{defi}{Definicja}[section]
+
+% koniec definicji
+
+\begin{document}
+\maketitle
+
+%tu idzie streszczenie na strone poczatkowa
+\begin{abstract}
+    % TODO
+\end{abstract}
+
+\tableofcontents
+%\listoffigures
+%\listoftables
+
+\chapter*{Introduction}
+\addcontentsline{toc}{chapter}{Introduction}
+
+\chapter{Preliminaries}\label{r:pojecia}
+
+% \begin{quote}
+  % Blaba, który jest blaba, nie jest prawdziwym blaba.
+
+% \raggedleft\slshape tłum. z~chińskiego Robert Blarbarucki
+% \end{quote}
+
+\section{Definitions}
+
+\chapter{Branch Infix Regular Queries}\label{r:branchinfix}
+
+\section{Word infix regular queries}
+
+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 afterwords is able to
+answer in time $O(1)$ questions of the form ``Is the infix $w[i, j]$ accepted by
+$A$?''. We present the full construction as we will be generalizing its
+internals for the tree case.
+
+Suppose $A$ is deterministic. We begin by replacing each letter of $w$ with the
+set of states of $A$, $Q$.
+
+Each letter $a$ of $w$ defines an injective function on $Q$, and we draw these
+functions as directed edges between successive copies of $Q$. For example, if
+$A$ in state $q$, reading $a$, would move to state $q'$, then, for any copy of
+$Q$ corresponding to an instance of $a$ in the original word, there will be an
+edge from $q$ there to $q'$ in the successive copy of $Q$.
+
+Now we will color the vertices of the graph we just constructed with the colors
+$1, 2, \ldots, |Q|$ in such a way that
+
+\begin{enumerate}
+    \item every copy of $Q$ has one vertex of each of the $|Q|$ colors;
+    \item when a vertex of color $i$ has an edge to a vertex of color $j$ in a
+        successive copy of $Q$, then $i \geq j$.
+\end{enumerate}
+
+The second point basically means that we will be trying to draw single-color
+paths, but when paths need to join, it is the higher-colored path that gets cut
+off.
+
+The construction is as follows:
+
+\begin{enumerate}
+    \item Color an arbitrary vertex of the first copy of $Q$ with the color $1$.
+    \item Follow the deterministic edges to the end of the word, coloring all
+        vertices along this path with $1$.
+    \item Now color another uncolored vertex of the first copy of $Q$ with the
+        color $2$.
+    \item Try following edges as far as possible, coloring all vertices with
+        $2$.
+    \item If your run into an already colored vertex, pick an arbitrary
+        uncolored vertex in this copy of $Q$ to color with $2$ and continue from
+        here.
+    \item Repeat steps 3.-5. for each successive color up to $|Q|$.
+\end{enumerate}
+
+Additionally, in each vertex, we store the index of the next copy of $Q$ in
+which the path of this vertex's color is broken by a lower color.
+
+\section{Least Common Ancestor via Range Minimum Query}
+
+\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$.
+
+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
+Schieber and Vishkin's structure for computing LCA queries. We will present our
+version of the structue in full detail, using Schieber and Vishkin's notation
+where possible.
+
+\subsection{High level overview}
+
+The LCA algorithm given by Schieber and Vishkin bases on two observations, first
+made by Harel and Tarjan:
+
+\begin{itemize}
+    \item LCA queries can be computed in constant time on \emph{simple paths}.
+    \item LCA queries can be computed in constant time on \emph{full binary trees}.
+\end{itemize}
+
+We map vertices of our tree $T$ to vertices of a full binary tree $B$ of size
+$O(n)$ that has two properties:
+
+\begin{enumerate}
+    \item The induced subgraph of all vertices mapped to the same node of $B$ is
+        a simple path in $T$.
+    \item If a vertex $v$ of $T$ is mapped to a vertex $b$ of $B$, all of its
+        descendants are mapped to descendants of $b$ (where $b$ is also a
+        descendant of itself).
+\end{enumerate}
+
+From 2. we get that also all of $v$'s ancestors are mapped to $b$'s ancestors in
+$B$, in particular they are all mapped into at most $\log(n)$ nodes of $B$.
+
+\section{Generalizing words to trees}
+
+\chapter{Conclusions}
+
+\end{document}
+
+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: t
+%%% coding: latin-2
+%%% End:
diff --git a/pracamgr.cls b/pracamgr.cls
new file mode 100644
index 0000000..6666254
--- /dev/null
+++ b/pracamgr.cls
@@ -0,0 +1,377 @@
+% Klasa dokumentow do skladu prac magisterskich i~licencjackich
+% na wydziale Matematyki, Mechaniki i~Informatyki UW.
+%
+% Copyright (c) 2001 by Wydzial Matematyki, Informatyki i Mechaniki.
+%
+% Zmiany 05.05.2006 by Seweryn Karlowicz
+%
+% Zmiany 03.01.2017 by Kuba Pochrybniak
+%
+% Zmiany 10.06.2020 by Paweł Goldstein
+
+\NeedsTeXFormat{LaTeX2e}
+\ProvidesClass{pracamgr}[2017/01/03 v0.7.0 Praca magisterska]
+\newif\ifmyclass@en
+\DeclareOption{en}{\myclass@entrue}
+\DeclareOption{pl}{\myclass@enfalse}
+\ExecuteOptions{pl}
+\ProcessOptions\relax
+
+\ifmyclass@en
+	\RequirePackage[english]{babel}
+	\RequirePackage[T1]{fontenc}
+\else
+	\RequirePackage[polish]{babel}
+	\RequirePackage[T1]{fontenc}
+\fi
+\RequirePackage[utf8]{inputenc}
+
+\def\@baseclass{report}
+\def\@rodzajpracy{\ifmyclass@en Master's\else magisterska\fi}
+\def\@stopien{\ifmyclass@en Master\else magister\fi}
+\DeclareOption{licencjacka}{
+	\def\@stopien{\ifmyclass@en Bachelor\else licencjat\fi}
+	\def\@rodzajpracy{\ifmyclass@en Bachelor's\else licencjacka\fi}
+}
+%\DeclareOption{licencjacka}{}
+\DeclareOption*{\PassOptionsToClass{\CurrentOption}{\@baseclass}}
+\PassOptionsToClass{a4paper,twoside,openright,11pt}{\@baseclass}
+\ProcessOptions
+
+\LoadClass{\@baseclass}
+
+\textwidth\paperwidth
+\advance\textwidth -55mm
+\oddsidemargin-1in
+\advance\oddsidemargin 30mm
+\evensidemargin-1in
+\advance\evensidemargin 25mm
+\topmargin -1in
+\advance\topmargin 2cm
+\setlength\textheight{48\baselineskip}
+\addtolength\textheight{\topskip}
+\marginparwidth15mm
+
+\newcounter{liczbaAutorow}
+\setcounter{liczbaAutorow}{0}
+\def\autor#1#2{\def\@imienazwisko{#1}\def\@album{#2}\stepcounter{liczbaAutorow}}
+\def\autori#1#2{\def\@imienazwiskoi{#1}\def\@albumi{#2}\stepcounter{liczbaAutorow}}
+\def\autorii#1#2{\def\@imienazwiskoii{#1}\def\@albumii{#2}\stepcounter{liczbaAutorow}}
+\def\autoriii#1#2{\def\@imienazwiskoiii{#1}\def\@albumiii{#2}\stepcounter{liczbaAutorow}}
+\def\autoriv#1#2{\def\@imienazwiskoiv{#1}\def\@albumiv{#2}\stepcounter{liczbaAutorow}}
+\def\autorv#1#2{\def\@imienazwiskov{#1}\def\@albumv{#2}\stepcounter{liczbaAutorow}}
+
+\autor{}{}
+\autori{}{}
+\autorii{}{}
+\autoriii{}{}
+\autoriv{}{}
+\autorv{}{}
+\setcounter{liczbaAutorow}{0}
+
+
+\newcommand{\autorZAlbumem}[2]{\begin{minipage}{0.45\textwidth}\centering{\Large\bfseries #1}\\[2mm]\ifmyclass@en Student no.\else Nr albumu:\fi\ #2\end{minipage}\ }
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Wersja angielska
+\ifmyclass@en
+	\renewcommand\maketitle{%
+	  \begin{titlepage}%
+		\let\footnotesize\small
+		\let\footnoterule\relax
+		\let \footnote \thanks
+		\begin{center}%
+		  {\LARGE\textbf{ University of Warsaw}\\
+			Faculty of Mathematics, Informatics and Mechanics\par}
+		  \vspace{1cm plus .5fill}
+		{
+			\setlength{\parindent}{0em}
+			\setlength{\baselineskip}{60pt}
+			\centering
+
+			\ifx\@imienazwisko\empty\else\autorZAlbumem{\@imienazwisko}{\@album}\fi
+			\ifx\@imienazwiskoi\empty\else\autorZAlbumem{\@imienazwiskoi}{\@albumi}\fi
+			\ifx\@imienazwiskoii\empty\else\autorZAlbumem{\@imienazwiskoii}{\@albumii}\fi
+			\ifx\@imienazwiskoiii\empty\else\autorZAlbumem{\@imienazwiskoiii}{\@albumiii}\fi
+			\ifx\@imienazwiskoiv\empty\else\autorZAlbumem{\@imienazwiskoiv}{\@albumiv}\fi
+			\ifx\@imienazwiskov\empty\else\autorZAlbumem{\@imienazwiskov}{\@albumv}\fi
+
+		}
+
+		  \vspace{8mm plus .5fill}
+		  {\Huge\textbf{\@title}\par}
+		  \vspace{8mm plus .1fill}
+		  {\large\bf \@rodzajpracy\ thesis\\[3pt]
+			in \MakeUppercase{\@kierunek} \\
+	%----zakres---
+			\@zakres \par}
+		  \vspace{2cm plus 1.5fill}
+		  \begin{flushright}\large
+			\begin{tabular}{l}
+			  Supervisor:\\
+			  \bfseries \@opiekun
+			\end{tabular}
+		  \end{flushright}
+		  \vspace{1cm plus 1fill}
+		  {\large Warsaw, \@date\par}
+		\end{center}
+		\@thanks
+		\end{titlepage}%
+		\begin{titlepage}
+	 		\c@page=2
+ 			\vfill \mbox{}
+	 	\end{titlepage}
+
+
+	  \begin{titlepage}
+	  \c@page=2
+	  \end{titlepage}
+	  \setcounter{footnote}{0}%
+	  \global\let\thanks\relax
+	  \global\let\maketitle\relax
+	  \global\let\@thanks\@empty
+	  \global\let\@author\@empty
+	  \global\let\@date\@empty
+	  \global\let\@title\@empty
+	  \global\let\title\relax
+	  \global\let\author\relax
+	  \global\let\date\relax
+	  \global\let\and\relax
+	}
+	\def\nralbumu#1{\gdef\@nralbumu{#1}}
+	\def\@nralbumu{???\ClassError{pracamgr}{Brak numeru albumu}\@ehc}
+	\def\kierunek#1{\gdef\@kierunek{#1}}
+	\def\@kierunek{???\ClassError{pracamgr}{Nie podano kierunku studiow}\@ehc}
+	%----zakres nie konieczny-----
+	\def\zakres#1{\gdef\@zakres{w zakresie \MakeUppercase{#1}}}
+	\def\@zakres{}
+	\def\opiekun#1{\gdef\@opiekun{#1}}
+	\def\@opiekun{???\ClassError{pracamgr}{Brak danych opiekuna pracy}\@ehc}
+	\def\keywords#1{\gdef\@keywords{#1}}
+	\def\@keywords{???\ClassError{pracamgr}{Brak slow kluczowych}\@ehc}
+	\def\dziedzina#1{\gdef\@dziedzina{#1}}
+	\def\@dziedzina{???\ClassError{pracamgr}{Brak dziedziny Socrates-Erasmus}\@ehc}
+	\def\klasyfikacja#1{\gdef\@klasyfikacja{#1}}
+	\def\@klasyfikacja{???\ClassError{pracamgr}{Brak klasyfikacji tematycznej}\@ehc}
+	%-------------------nowe------------
+	\def\tytulang#1{\gdef\@tytulang{#1}}
+	\def\@tytulang{???\ClassError{pracamgr}{Brak tytulu po angielsku}\@ehc}
+	\def\titlepl#1{\gdef\@titlepl{#1}}
+	\def\@titlepl{???\ClassError{pracamgr}{Brak tytulu po polsku}\@ehc}
+
+
+	\renewenvironment{abstract}{%
+	  \titlepage
+	  \null\nobreak\vfil
+	  \@beginparpenalty\@lowpenalty
+	  \begin{center}%
+		\bfseries\large \abstractname
+		\@endparpenalty\@M
+	  \end{center}}%
+	{\par
+	  \vspace*{26pt}%
+	  \begin{center}%
+		\bfseries\large Keywords
+		\@endparpenalty\@M
+	  \end{center}
+	  \@keywords\par
+	  \vspace*{26pt}%
+	  \begin{center}%
+		\bfseries\large Thesis domain (Socrates-Erasmus subject area codes)
+		\@endparpenalty\@M
+	  \end{center}
+	   \@dziedzina\par
+	  \vspace*{26pt}%
+	  \begin{center}%
+		\bfseries\large Subject classification
+		\@endparpenalty\@M
+	  \end{center}
+	  \@klasyfikacja\par
+	  \vspace*{26pt}%
+	  \begin{center}%
+		\begingroup
+		\bfseries\large Tytuł pracy w języku polskim
+		\@endparpenalty\@M
+		\endgroup
+
+		\medskip
+		\@titlepl\par
+	  \end{center}
+	  \vspace*{26pt}%
+	%-------------------nowosc----------------
+	  \nobreak\vfil\null\endtitlepage\cleardoublepage}
+
+
+\def\cleardoublepage{\clearpage\if@twoside \ifodd\c@page\else
+    \hbox{}\thispagestyle{empty}\newpage\if@twocolumn\hbox{}\newpage\fi\fi\fi}
+
+\renewcommand*\@seccntformat[1]{\csname the#1\endcsname.\enspace}
+\def\numberline#1{\hb@xt@\@tempdima{#1.\hfil}}
+\renewcommand*\l@chapter[2]{%
+  \ifnum \c@tocdepth >\m@ne
+    \addpenalty{-\@highpenalty}%
+    \vskip 1.0em \@plus\p@
+    \setlength\@tempdima{1.5em}%
+    \begingroup
+      \parindent \z@ \rightskip \@pnumwidth
+      \parfillskip -\@pnumwidth
+      \leavevmode \bfseries
+      \advance\leftskip\@tempdima
+      \hskip -\leftskip
+      #1\nobreak\mdseries
+      \leaders\hbox{$\m@th
+        \mkern \@dotsep mu\hbox{.}\mkern \@dotsep
+        mu$}\hfill
+      \nobreak\hb@xt@\@pnumwidth{\hss #2}\par
+      \penalty\@highpenalty
+    \endgroup
+  \fi}
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Wersja polska
+\else
+
+	\renewcommand\maketitle{%
+	  \begin{titlepage}%
+		\let\footnotesize\small
+		\let\footnoterule\relax
+		\let \footnote \thanks
+		\begin{center}%
+		  {\LARGE\textbf{Uniwersytet Warszawski}\\
+			Wydzia\l{} Matematyki, Informatyki i Mechaniki\par}
+		  \vspace{1cm plus .5fill}
+		{
+			\setlength{\parindent}{0em}
+			%\setlength{\baselineskip}{60pt}
+			\centering
+
+				\ifx\@imienazwisko\empty\else\autorZAlbumem{\@imienazwisko}{\@album}\fi
+				\ifx\@imienazwiskoi\empty\else\autorZAlbumem{\@imienazwiskoi}{\@albumi}\fi
+				\ifx\@imienazwiskoii\empty\else\autorZAlbumem{\@imienazwiskoii}{\@albumii}\fi
+				\ifx\@imienazwiskoiii\empty\else\autorZAlbumem{\@imienazwiskoiii}{\@albumiii}\fi
+				\ifx\@imienazwiskoiv\empty\else\autorZAlbumem{\@imienazwiskoiv}{\@albumiv}\fi
+				\ifx\@imienazwiskov\empty\else\autorZAlbumem{\@imienazwiskov}{\@albumv}\fi
+
+		}
+
+		  \vspace{8mm plus .5fill}
+		  {\Huge\textbf{\@title}\par}
+		  \vspace{8mm plus .1fill}
+		  {\large\bf Praca \@rodzajpracy\\[3pt]
+			na kierunku \MakeUppercase{\@kierunek} \\
+	%----zakres---
+			\@zakres \par}
+		  \vspace{2cm plus 1.5fill}
+		  \begin{flushright}\large
+			\begin{tabular}{l}
+			  Praca wykonana pod kierunkiem\\
+			  \bfseries \@opiekun
+			\end{tabular}
+		  \end{flushright}
+		  \vspace{1cm plus 1fill}
+		  {\large Warszawa, \@date\par}
+		\end{center}
+		\@thanks
+	  \end{titlepage}%
+	   \begin{titlepage}
+	  \c@page=2
+	\vfill \mbox{}
+	  \end{titlepage}
+
+	  \setcounter{footnote}{0}%
+	  \global\let\thanks\relax
+	  \global\let\maketitle\relax
+	  \global\let\@thanks\@empty
+	  \global\let\@author\@empty
+	  \global\let\@date\@empty
+	  \global\let\@title\@empty
+	  \global\let\title\relax
+	  \global\let\author\relax
+	  \global\let\date\relax
+	  \global\let\and\relax
+	}
+	\def\nralbumu#1{\gdef\@nralbumu{#1}}
+	\def\@nralbumu{???\ClassError{pracamgr}{Brak numeru albumu}\@ehc}
+	\def\kierunek#1{\gdef\@kierunek{#1}}
+	\def\@kierunek{???\ClassError{pracamgr}{Nie podano kierunku studiow}\@ehc}
+	%----zakres nie konieczny-----
+	\def\zakres#1{\gdef\@zakres{w zakresie \MakeUppercase{#1}}}
+	\def\@zakres{}
+	\def\opiekun#1{\gdef\@opiekun{#1}}
+	\def\@opiekun{???\ClassError{pracamgr}{Brak danych opiekuna pracy}\@ehc}
+	\def\keywords#1{\gdef\@keywords{#1}}
+	\def\@keywords{???\ClassError{pracamgr}{Brak slow kluczowych}\@ehc}
+	\def\dziedzina#1{\gdef\@dziedzina{#1}}
+	\def\@dziedzina{???\ClassError{pracamgr}{Brak dziedziny Socrates-Erasmus}\@ehc}
+	\def\klasyfikacja#1{\gdef\@klasyfikacja{#1}}
+	\def\@klasyfikacja{???\ClassError{pracamgr}{Brak klasyfikacji tematycznej}\@ehc}
+	%-------------------nowe------------
+	\def\tytulang#1{\gdef\@tytulang{#1}}
+	\def\@tytulang{???\ClassError{pracamgr}{Brak tytulu po angielsku}\@ehc}
+
+
+	\renewenvironment{abstract}{%
+	  \titlepage
+	  \null\nobreak\vfil
+	  \@beginparpenalty\@lowpenalty
+	  \begin{center}%
+		\bfseries\large \abstractname
+		\@endparpenalty\@M
+	  \end{center}}%
+	{\par
+	  \vspace*{26pt}%
+	  \begin{center}%
+		\bfseries\large Słowa kluczowe
+		\@endparpenalty\@M
+	  \end{center}
+	  \@keywords\par
+	  \vspace*{26pt}%
+	  \begin{center}%
+		\bfseries\large Dziedzina pracy (kody wg programu Socrates-Erasmus)
+		\@endparpenalty\@M
+	  \end{center}
+	   \@dziedzina\par
+	  \vspace*{26pt}%
+	  \begin{center}%
+		\bfseries\large Klasyfikacja tematyczna
+		\@endparpenalty\@M
+	  \end{center}
+	  \@klasyfikacja\par
+	  \vspace*{26pt}%
+	%-------------------nowosc----------------
+	  \begin{center}%
+		\bfseries\large Tytuł pracy w języku angielskim
+		\@endparpenalty\@M
+	  \end{center}
+	  \@tytulang\par
+	  \nobreak\vfil\null\endtitlepage\cleardoublepage}
+
+	\def\cleardoublepage{\clearpage\if@twoside \ifodd\c@page\else
+		\hbox{}\thispagestyle{empty}\newpage\if@twocolumn\hbox{}\newpage\fi\fi\fi}
+
+	\renewcommand*\@seccntformat[1]{\csname the#1\endcsname.\enspace}
+	\def\numberline#1{\hb@xt@\@tempdima{#1.\hfil}}
+	\renewcommand*\l@chapter[2]{%
+	  \ifnum \c@tocdepth >\m@ne
+		\addpenalty{-\@highpenalty}%
+		\vskip 1.0em \@plus\p@
+		\setlength\@tempdima{1.5em}%
+		\begingroup
+		  \parindent \z@ \rightskip \@pnumwidth
+		  \parfillskip -\@pnumwidth
+		  \leavevmode \bfseries
+		  \advance\leftskip\@tempdima
+		  \hskip -\leftskip
+		  #1\nobreak\mdseries
+		  \leaders\hbox{$\m@th
+			\mkern \@dotsep mu\hbox{.}\mkern \@dotsep
+			mu$}\hfill
+		  \nobreak\hb@xt@\@pnumwidth{\hss #2}\par
+		  \penalty\@highpenalty
+		\endgroup
+	  \fi}
+
+\fi
+
+
+\endinput