diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-11-05 12:20:27 +0100 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2021-11-05 12:20:27 +0100 |
commit | 99c36deb1ec967327190af8dc412e8362e49dbd3 (patch) | |
tree | 0bb23f954ebf91a55ffee24336f00f8f68722d58 /mgr.tex | |
parent | 840dfd0f4eee7fd1f7f9b0035de72b9ec2d29a89 (diff) |
Add BojaĆczyk citation
Diffstat (limited to 'mgr.tex')
-rw-r--r-- | mgr.tex | 16 |
1 files changed, 8 insertions, 8 deletions
@@ -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 |