Arnab Bhattacharyya, Palash Dey, et al.
SIGMOD/PODS 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 algorithm that runs in linear time when the number of necessary edits is small. More precisely, our algorithm runs in O(n) + dO(1) time, where n is the length of the sequence to be fixed and d is the minimum number of edits. The problem of fixing parentheses sequences is related to the task of repairing semi-structured documents such as XML and JSON.
Arnab Bhattacharyya, Palash Dey, et al.
SIGMOD/PODS 2016
Artur Czumaj, Jakub Lacki, et al.
SIAM Journal on Computing
Alexandr Andoni, Aleksandar Nikolov, et al.
STOC 2014
Krzysztof Onak, Xiaorui Sun
AISTATS 2018