From 9436701bc08ed12318a66ea94d209a5a9b23648f Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Mon, 19 Dec 2022 23:20:36 +0100 Subject: Fix time complexity --- mgr.tex | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) diff --git a/mgr.tex b/mgr.tex index 787cd91..5b9f987 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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} -- cgit v1.2.3