4
$\begingroup$

Given a word $w$ over $\{ [, ] \}$, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make $w$ a Dyck word, i.e., a word in which the squared brackets are balanced.

I can imagine a few practical applications, but my bibliography search yielded nothing. It looks like dynamic programming though. Any ideas?

$\endgroup$
4
  • 1
    $\begingroup$ Check: arxiv.org/pdf/1904.08402.pdf $\endgroup$ Mar 6 at 19:15
  • $\begingroup$ That's an interesting problem! what about the immediate generalization from Dyck languages to context-free languages, have you looked for literature on that question? $\endgroup$
    – a3nm
    Mar 12 at 11:38
  • $\begingroup$ Or maybe even something easier: what about visibly pushdown languages? $\endgroup$ Mar 12 at 22:03
  • 1
    $\begingroup$ Btw, might be related: arxiv.org/pdf/1504.08259 $\endgroup$ Mar 12 at 22:07
4
$\begingroup$

The generalized problem, concerning Dyck($s$), for $s$ distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled The Dyck Language Edit Distance Problem in Near-linear Time

B. Saha, "The Dyck Language Edit Distance Problem in Near-Linear Time," 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 2014, pp. 611-620, doi: 10.1109/FOCS.2014.71.

Indeed, the problem is easy for $s=1$. For $s\ge2$ the exact complexity is not known. The classical techniques for correcting context-free languages are $O(sn^3)$ (Valiant 1975). On the other hand, the usual string editing problem which can be solved in quadratic time can be reduced to Dyck($s$).

Saha's result gives a nearly linear time algorithm that returns an approximation of the true edit distance. I am not sure whether this algorithm can produce the edit sequence.

$\endgroup$
3
$\begingroup$

If by "edit operations" you mean single character insertions, deletions, and substitutions then I believe a greedy algorithm works.

Let $x_i$ be the number of ] minus the number of [ in the first $i$ characters. Every edit operation changes each $x_i$ by at most 2. Hence you will need at least $\lceil \frac {\max x_i} 2 \rceil$ operations to correct the word. One way to achieve this is to substitute all the earliest ] for [ and delete one ] if the number is odd.

Finally, you need $x_n$ to be 0. The above operations will reduce $x_n$ by $\max x_i$ and this is unavoidable, since an operation at position $i$ affects exactly those positions after $i$ and by an equal amount. Hence you will need a final $\lceil \frac {\max x_i - x_n} 2 \rceil$ operations to finish correcting the word. One way to achieve this is to substitute the latest [ for ] and delete one [ if the number is odd.

Since the solution is so simple, I doubt there's any literature on it.

$\endgroup$
2
  • $\begingroup$ I am not sure I understand what you mean by saying: "One way to achieve this is to substitute all the earliest ] for [ and delete one ] if the number is odd." Do you mean this is what you do when xi is positive? $\endgroup$
    – Yossi Gil
    Mar 10 at 16:58
  • $\begingroup$ $\max x_i$ and $\max x_i - x_n$ are always nonnegative so yes. $\endgroup$ Mar 11 at 10:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.