Jennifer Todtenhoefer

Highlights Conference 2025 Conference Abstract

Recent results in work-sensitive dynamic complexity

• Jennifer Todtenhoefer

Highlights Conference 2023 Conference Abstract

On the work of dynamic constant-time parallel algorithms for regular tree languages and context-free languages

• Jennifer Todtenhoefer

Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the goal to minimise work (or equivantly, the number of processors). In fact, their inspection yields the work bounds O(n^2) and O(n^7) per change operation, respectively. In this talk, dynamic algorithms for regular tree languages are proposed that generalise the previous algorithms in that they allow unbounded node rank and leaf insertions, while improving the work bound from O(n^2) to O(n^ϵ), for arbitrary ϵ > 0. For context-free languages algorithms with better work bounds (compared with O(n^7)) for restricted classes are proposed: for every ϵ > 0 there are such algorithms for deterministic context-free languages with work bound O(n^(3+ϵ)) and for visibly pushdown languages with work bound O(n^(2+ϵ)). This talk is based on joint work with Jonas Schmidt and Thomas Schwentick. Contributed talk given by Jennifer Todtenhoefer

MFCS Conference 2023 Conference Paper

On the Work of Dynamic Constant-Time Parallel Algorithms for Regular Tree Languages and Context-Free Languages

• Jonas Schmidt 0001
• Thomas Schwentick
• Jennifer Todtenhoefer

Previous work on Dynamic Complexity has established that there exist dynamic constant-time parallel algorithms for regular tree languages and context-free languages under label or symbol changes. However, these algorithms were not developed with the goal to minimise work (or, equivalently, the number of processors). In fact, their inspection yields the work bounds 𝒪(n²) and 𝒪(n⁷) per change operation, respectively. In this paper, dynamic algorithms for regular tree languages are proposed that generalise the previous algorithms in that they allow unbounded node rank and leaf insertions, while improving the work bound from 𝒪(n²) to 𝒪(n^ε), for arbitrary ε > 0. For context-free languages, algorithms with better work bounds (compared with 𝒪(n⁷)) for restricted classes are proposed: for every ε > 0 there are such algorithms for deterministic context-free languages with work bound 𝒪(n^{3+ε}) and for visibly pushdown languages with work bound 𝒪(n^{2+ε}).