# The Dyck Language Correction Problem

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?

• Mar 6 '21 at 19:15
• 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?
– a3nm
Mar 12 '21 at 11:38
• Or maybe even something easier: what about visibly pushdown languages? Mar 12 '21 at 22:03
• Btw, might be related: arxiv.org/pdf/1504.08259 Mar 12 '21 at 22:07

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.

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.

• 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? Mar 10 '21 at 16:58
• $\max x_i$ and $\max x_i - x_n$ are always nonnegative so yes. Mar 11 '21 at 10:39