m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2022-10-21 16:37:11 +0200
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2022-10-21 16:37:11 +0200
commitf2fc04e29f662c1876edac9f270c1673c350253c (patch)
treee41ae413ef8f6eb66bd464fe0a923a63fd198881
parent0ca2dd97150a7584b2081ebed6f3cdf18b5fb8cd (diff)
Cite Kazana's query answering work
-rw-r--r--mgr.tex12
1 files changed, 7 insertions, 5 deletions
diff --git a/mgr.tex b/mgr.tex
index 777c460..8b1ea5a 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -180,11 +180,13 @@ free variables are all first-order is in \constantdelaylin, and
factorization forests due to \textcite{colcombet} rather than Bagan's intricate
indexing structure.
-Colcombet's factorization could likely be used to solve the problem of branch
-infix regular questions, which we introduce as a subproblem of MSO query
-answering in Chapter \ref{branchinfix}. However, Colcombet's result depends on
-applications of semigroup theory. We present a much more straightforward
-algorithmic approach.
+Most closely related, \textcite{kazanaphd} showed that MSO query answering on
+structures of bounded treewidth is \constantdelaylin in his PhD thesis, however
+this result was limited to MSO queries with only first-order variables. This
+work generalizes to also allowing set variables in the query, and uses a
+different approach. Here again Kazana relied on Colcombet's factorization, an
+application of semigroup theory. Our appraoch is more algorithmic and
+straigforward.
\section{Organization}