diff options
Diffstat (limited to 'presentation/presentation.md')
| -rw-r--r-- | presentation/presentation.md | 16 |
1 files 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 |