A Dyck sequence is a sequence of opening and closing parentheses (of various types) that is balanced. The Dyck edit distance of a given sequence of parentheses $S$ is the smallest number of edit operations (insertions, deletions, and substitutions) needed to transform $S$ into a Dyck sequence. We consider the threshold Dyck edit distance problem, where the input is a sequence of parentheses $S$ and a positive integer $k$, and the goal is to compute the Dyck edit distance of $S$ only if the distance is at most $k$, and otherwise report that the distance is larger than $k$. Backurs and Onak [PODS'16] showed that the threshold Dyck edit distance problem can be solved in $O(n+k^{16})$ time. In this work, we design new algorithms for the threshold Dyck edit distance problem which costs $O(n+k^{4.544184})$ time with high probability or $O(n+k^{4.853059})$ deterministically. Our algorithms combine several new structural properties of the Dyck edit distance problem, a refined algorithm for fast $(\min,+)$ matrix product, and a careful modification of ideas used in Valiant's parsing algorithm.
翻译:Dyck 序列是一个平衡的打开和关闭括号(不同类型)的序列。 括号中一个特定序列的 Dyck 编辑距离 $S$是将美元转换成 Dyck 序列所需的最小编辑操作数量( 插入、 删除和替换 ) 。 我们考虑门槛 Dyck 编辑距离问题, 输入是圆括号序列 $S 美元和正整数美元, 目标是计算Dyck编辑距离( 以距离最多 $为美元) $S 的距离, 或者报告距离大于 $k$。 后端和 Onak [ PODS 16] 显示, 门槛 Dyck 编辑距离问题可以用$O( n+k ⁇ 16}) 时间来解决。 在这项工作中, 我们为门槛 Dyck编辑问题设计了新的算法, 花费$O( n+k ⁇ 4. 44184} 时间或$O( n+k ⁇ 4. 853059} 确定距离大于美元。 我们的算算算法将一些新的结构属性变数, 用于快速的快速分析。