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