From 99c36deb1ec967327190af8dc412e8362e49dbd3 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 5 Nov 2021 12:20:27 +0100 Subject: =?UTF-8?q?Add=20Boja=C5=84czyk=20citation?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- mgr.bib | 11 +++++++++++ mgr.tex | 16 ++++++++-------- 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 -- cgit v1.2.3