Dynamic Dyck and Tree Edit Distance: Decompositions and Reductions to String Edit Distance

Debarati Das, Jacob Gilbert, MohammadTaghi Hajiaghayi +2

We present the first dynamic algorithms for Dyck and tree edit distances with subpolynomial update times. Dyck edit distance measures how far a parenthesis string is from a well-pa…