m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-11-05 12:20:27 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-11-05 12:20:27 +0100
commit99c36deb1ec967327190af8dc412e8362e49dbd3 (patch)
tree0bb23f954ebf91a55ffee24336f00f8f68722d58
parent840dfd0f4eee7fd1f7f9b0035de72b9ec2d29a89 (diff)
Add Bojańczyk citation
-rw-r--r--mgr.bib11
-rw-r--r--mgr.tex16
2 files changed, 19 insertions, 8 deletions
diff --git a/mgr.bib b/mgr.bib
index d29d7e5..496f0ed 100644
--- a/mgr.bib
+++ b/mgr.bib
@@ -99,3 +99,14 @@
author = {Jörg Flum and Markus Frick and Martin Grohe},
title = {Query Evaluation via Tree-Decompositions}
}
+@misc{bojanczyk,
+ url = {https://www.mimuw.edu.pl/~bojan/upload/confdltBojanczyk09.pdf},
+ year = 2009,
+ % month = {dec},
+ % publisher = {Society for Industrial {\&} Applied Mathematics ({SIAM})},
+ % volume = {17},
+ % number = {6},
+ pages = {8--10},
+ author = {Mikołaj Bojańczyk},
+ title = {Factorization Forests}
+}
diff --git a/mgr.tex b/mgr.tex
index d3aa05c..bf59c43 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -386,14 +386,14 @@ automaton we ``don't care'' about the exponential cost of determinizing it.
j]$ belong to $L$?
}
-This problem has a very elegant \qpoptimal{} solution. We present the full
-construction as we will be generalizing its internals for the tree case in
-Chapter \ref{branchinfix}.
-
-\textbf{preprocessing} We begin by replacing each letter of $w$ with a copy of the set of states of
-$A$, $Q$. More precisely, we will be working with a graph whose vertex set is
-$\{1, \ldots, |w|\} \times Q$. We will refer to a vertex in the $i$th copy of
-$Q$ labeled with state $q$ as $i.q$.
+This problem has a very elegant \qpoptimal{} solution, as presented by
+\textcite{bojanczyk}. We present the full construction as we will be
+generalizing its internals for the tree case in Chapter \ref{branchinfix}.
+
+\textbf{preprocessing} We begin by replacing each letter of $w$ with a copy of
+the set of states of $A$, $Q$. More precisely, we will be working with a graph
+whose vertex set is $\{1, \ldots, |w|\} \times Q$. We will refer to a vertex in
+the $i$th copy of $Q$ labeled with state $q$ as $i.q$.
Since $A$ is deterministic, each letter $a \in \Sigma$ can be seen as a function
$a : Q \to Q$, and we draw these functions as directed edges between successive