m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
path: root/presentation/presentation.md
diff options
context:
space:
mode:
Diffstat (limited to 'presentation/presentation.md')
-rw-r--r--presentation/presentation.md16
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