From 1c2aa53edc01aae92c47e585fd8ae0649f213bea Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sun, 18 Dec 2022 17:14:11 +0100 Subject: Be more brief --- presentation/presentation.md | 16 +++++++--------- 1 file changed, 7 insertions(+), 9 deletions(-) diff --git a/presentation/presentation.md b/presentation/presentation.md index e2898d4..d3ab7be 100644 --- a/presentation/presentation.md +++ b/presentation/presentation.md @@ -69,8 +69,7 @@ singletons. * I show an $\langle O_{\varphi}(n), O_{\varphi}(m \log{m}) \rangle$ solution to MSO query answering. -* Answering is $O_{\varphi}(1)$ when restricting to only first-order free - variables, matching Kazana's result. +* $O_{\varphi}(1)$ for first-order free variables, matching Kazana's result. * Should be understandable by a CS student who has taken undergraduate algorithmics and automata theory courses. @@ -117,16 +116,15 @@ Note: computing the partition takes time $O(m \log{m})$ as it uses a sort. ## Computing Roots of Parts - Subtree -* During preprocessing, we precomputed a run of $A$ over $T$. -* In a subtree part, no vertices other than the root were relabeled. -* So we can apply $A$'s transition function to the precomputed states of the - root's children, and the root's new label. +* During preprocessing, we precompute $A$'s run over $T$. +* In a subtree part, only the root was relabeled. +* Apply $A$'s transition function to the precomputed states of the root's + children and the root's new label. ## Computing Roots of Parts - Singleton * Both of the singleton's children are roots of parts. -* Since we're working bottom-up, we've already computed the states in the roots - of those. +* We're working bottom-up, we've already computed the states in those roots. * Apply $A$'s transition function to those and the singleton's new label. ## Computing Roots of Parts - Subtree With a Hole @@ -135,7 +133,7 @@ Note: computing the partition takes time $O(m \log{m})$ as it uses a sort. * Idea: can be computed by a DFA walking up from hole to root. * Chapter 3: Branch Infix Regular Questions * Show how to solve this in $\langle O_A(n), O_A(1) \rangle$. - * Generalization of a clever algorithm on words. + * Generalization of a known algorithm on words. ## Computing Roots of Parts - Subtree With a Hole -- cgit v1.2.3