diff options
| -rw-r--r-- | mgr.tex | 15 |
1 files changed, 8 insertions, 7 deletions
@@ -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? |