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.782036})$ 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$, 否则报告距离大于 $k$。 Backurs 和 Onak [PODS'16] 显示, 门槛 Dyck 编辑距离问题可以在$O (n+k}16}) 时间中解决。 在这项工作中, 我们为门槛 Dyckn 编辑问题设计了新的算法, 费用为 $O (n+k ⁇ 4. 470. 2036} 时间和 $O (n+k ⁇ 4. 853059} 美元, 否则报告距离大于 美元。 。 。 。 后端和 Oclcalqalcalsalsals 将一些新的结构变换的快速分析器, 用于美元的快速分析。

0
下载
关闭预览

相关内容

专知会员服务
123+阅读 · 2020年9月8日
【斯坦福大学Chelsea Finn-NeurIPS 2019】贝叶斯元学习
专知会员服务
37+阅读 · 2019年12月17日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
RL 真经
CreateAMind
5+阅读 · 2018年12月28日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
条件GAN重大改进!cGANs with Projection Discriminator
CreateAMind
8+阅读 · 2018年2月7日
Capsule Networks解析
机器学习研究会
11+阅读 · 2017年11月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top
微信扫码咨询专知VIP会员