From 21d71bd5446af1d6ad714620155e0d98e8a3efa7 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Mon, 21 Nov 2022 13:43:41 +0100 Subject: Fix wording --- mgr.tex | 15 ++++++++------- 1 file 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? -- cgit v1.2.3