diff options
| -rw-r--r-- | mgr.bib | 38 | ||||
| -rw-r--r-- | mgr.tex | 11 |
2 files changed, 46 insertions, 3 deletions
@@ -0,0 +1,38 @@ +@incollection{bagan2006, + doi = {10.1007/11874683_11}, + % url = {https://doi.org/10.1007%2F11874683_11}, + year = 2006, + publisher = {Springer Berlin Heidelberg}, + pages = {167--181}, + author = {Guillaume Bagan}, + title = {{MSO} Queries on Tree Decomposable Structures Are Computable with Linear Delay} +} +@article{kazana2013, + doi = {10.1145/2528928}, + % url = {https://doi.org/10.1145%2F2528928}, + year = 2013, + month = {nov}, + publisher = {Association for Computing Machinery ({ACM})}, + volume = {14}, + number = {4}, + pages = {1--12}, + author = {Wojciech Kazana and Luc Segoufin}, + title = {Enumeration of monadic second-order queries on trees} +} +@incollection{colcombet, + doi = {10.1007/978-3-540-73420-8_77}, + % url = {https://doi.org/10.1007%2F978-3-540-73420-8_77}, + publisher = {Springer Berlin Heidelberg}, + pages = {901--912}, + author = {Thomas Colcombet}, + title = {A Combinatorial Theorem for Trees} +} +@incollection{bender2000, + doi = {10.1007/10719839_9}, + % url = {https://doi.org/10.1007%2F10719839_9}, + year = 2000, + publisher = {Springer Berlin Heidelberg}, + pages = {88--94}, + author = {Michael A. Bender and Mart{\'{\i}}n Farach-Colton}, + title = {The {LCA} Problem Revisited} +} @@ -3,6 +3,9 @@ \documentclass[en]{pracamgr} \usepackage{definitions} +\usepackage[backend=biber]{biblatex} +\addbibresource{mgr.bib} + % Dane magistranta: \autor{Marcin Chrzanowski}{370754} @@ -50,7 +53,7 @@ between nodes $x$ and $y$ belong to the regular language $L$'' (for a previously fixed regular language $L$) in the same time complexities. Our approach is much simpler in presentation than a previously known solution - due to Colcombet. + due to \textcite{colcombet}. \end{abstract} \tableofcontents @@ -267,8 +270,8 @@ We can now reduce the problem to the following: 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 -Bender and Farach-Colton's presentation of an algorithm originally described by -Berkman and Vishkin for computing LCA queries. +\textcite{bender2000}, where a simple algorithm for computing LCA queries is +presented. First, let's define an auxillary problem we will use, that of Range Minimum Queries (RMQ): @@ -326,6 +329,8 @@ h \chapter{Conclusions} +\printbibliography + \end{document} %%% Local Variables: |