diff options
author | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2022-10-21 16:37:11 +0200 |
---|---|---|
committer | Marcin Chrzanowski <mc370754@students.mimuw.edu.pl> | 2022-10-21 16:37:11 +0200 |
commit | f2fc04e29f662c1876edac9f270c1673c350253c (patch) | |
tree | e41ae413ef8f6eb66bd464fe0a923a63fd198881 | |
parent | 0ca2dd97150a7584b2081ebed6f3cdf18b5fb8cd (diff) |
Cite Kazana's query answering work
-rw-r--r-- | mgr.tex | 12 |
1 files changed, 7 insertions, 5 deletions
@@ -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} |