From 7bb424b859ff58d360aa9ba7578edc8caebf69fe Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Fri, 13 Aug 2021 10:44:19 -0400 Subject: Fix time complexity in abstract --- mgr.tex | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) diff --git a/mgr.tex b/mgr.tex index 919a9b8..cd44d87 100644 --- a/mgr.tex +++ b/mgr.tex @@ -46,14 +46,14 @@ We define relabel regular queries on trees, which, via the known equivalence between tree automata and MSO formulae on trees, happens to be a generalization of the MSO query answering problem on trees. We show these - queries can be performed in linear time with respect to query size (constant - time in the case of MSO formulae with only first-order free variables) after - preprocessing the input tree in linear time. Along the way, we show an - algorithm for handling queries of the form ``Does the infix of a tree branch - between nodes $x$ and $y$ belong to the regular language $L$'' (for a - previously fixed regular language $L$) in the same time complexities. Our - approach is much simpler in presentation than a previously known solution - due to \textcite{colcombet}. + queries can be performed in time $O(m \log(m))$ with respect to query size + (constant time in the case of MSO formulae with only first-order free + variables) after preprocessing the input tree in linear time. Along the way, + we show an algorithm for handling queries of the form ``Does the infix of a + tree branch between nodes $x$ and $y$ belong to the regular language $L$'' + (for a previously fixed regular language $L$) in constant time after linear + preprocessing. Our approach is much simpler in presentation than a + previously known solution due to \textcite{colcombet}. \end{abstract} \tableofcontents -- cgit v1.2.3