Krzysztof Onak

Fast Algorithms for Parsing Sequences of Parentheses with Few Errors

2016

We consider the problem of fixing sequences of unbalanced parentheses. A classic algorithm based on dynamic programming computes the optimum sequence of edits required to solve the problem in cubic time. We show the first …