m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--mgr.tex15
1 files changed, 8 insertions, 7 deletions
diff --git a/mgr.tex b/mgr.tex
index 8463780..23a7af7 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -183,10 +183,11 @@ indexing structure.
Most closely related, \textcite{kazanaphd} showed that MSO query answering
(there called \emph{query testing}) 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.
+queries whose free variables are first-order variables (i.e., range over single
+vertices). 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}
@@ -1294,9 +1295,9 @@ problem
}{%
given a set of tree vertices $S$, compute the LCA closure of $S$.
}
-has an \qptime{$O(|T|)$}{$|S| \log |S|$} solution. An open question is whether
-this is an optimal solution. If the question answering step's complexity could
-be reduced to $O(|S|)$, MSO query answering on structures of bounded treewidth
+has an \qptime{$O(|T|)$}{$|S| \log |S|$} solution. We do not know whether this
+is an optimal solution. If the question answering step's complexity could be
+reduced to $O(|S|)$, MSO query answering on structures of bounded treewidth
would then be known to be in \lineardelaylin. Or is there a lower bound on
computing LCA closures in this setting, for example, would it be possible to
reduce comparison sorting to computing LCA closures?