diff options
| -rw-r--r-- | mgr.tex | 17 |
1 files changed, 9 insertions, 8 deletions
@@ -182,14 +182,15 @@ free variables are all first-order is in \constantdelaylin, and factorization forests due to \textcite{colcombet} rather than Bagan's intricate 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 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. +Most closely related, \textcite{kazanaphd} investigated MSO query answering +(there called \emph{query testing}) on structures of bounded treewidth in his +PhD thesis. He showed that after linear preprocessing, questions can be answered +in constant time, however this result was limited to MSO 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} |