diff options
| -rw-r--r-- | mgr.tex | 175 | ||||
| -rw-r--r-- | pracamgr.cls | 377 |
2 files changed, 552 insertions, 0 deletions
@@ -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 |