An Improved Algorithm for The $k$-Dyck Edit Distance Problem
العنوان: | An Improved Algorithm for The $k$-Dyck Edit Distance Problem |
---|---|
المؤلفون: | Dvir Fried, Shay Golan, Tomasz Kociumaka, Tsvi Kopelowitz, Ely Porat, Tatiana Starikovskaya |
المساهمون: | Bar-Ilan University [Israël], Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS) |
المصدر: | 33rd SODA 2022 33rd SODA 2022, 2022, Alexandria ( Virtual Conference), United States |
سنة النشر: | 2021 |
مصطلحات موضوعية: | FOS: Computer and information sciences, Computer Science - Data Structures and Algorithms, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs] |
الوصف: | 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. Journal version |
اللغة: | English |
URL الوصول: | https://explore.openaire.eu/search/publication?articleId=doi_dedup___::991d0182ea9380d38340f512bd19bb61 http://arxiv.org/abs/2111.02336 |
حقوق: | OPEN |
رقم الأكسشن: | edsair.doi.dedup.....991d0182ea9380d38340f512bd19bb61 |
قاعدة البيانات: | OpenAIRE |
الوصف غير متاح. |