  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 $O(n^2)$ and
$O(n^7)$ 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 $O(n^2)$ to $O(n^{\epsilon})$, for arbitrary $\epsilon > 0$.
For context-free languages, algorithms with better work bounds (compared with
$O(n^7)$) for restricted classes are proposed: for every $\epsilon > 0$ there
are such algorithms for deterministic context-free languages with work bound
$O(n^{3+\epsilon})$ and for visibly pushdown languages with work bound
$O(n^{2+\epsilon})$.
