<p>The generalized problem, concerning Dyck(<span class="math-container">$s$</span>), for <span class="math-container">$s$</span> distinct pairs of parenthesis, was studied by Barna Saha in a paper entitled <em>The Dyck Language Edit Distance Problem in Near-linear Time</em></p>
<p>B. Saha, &quot;The Dyck Language Edit Distance Problem in Near-Linear Time,&quot; 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, Philadelphia, PA, USA, 2014, pp. 611-620, doi: 10.1109/FOCS.2014.71.</p>
<p>Indeed, the problem is easy for <span class="math-container">$s=1$</span>. For <span class="math-container">$s\ge2$</span> the exact complexity is not known. The classical techniques for correcting context-free languages are <span class="math-container">$O(sn^3)$</span> (Valiant 1975). On the other hand, the usual string editing problem which can be solved in quadratic time can be reduced to Dyck(<span class="math-container">$s$</span>).</p>
<p>Saha's result gives a nearly linear time algorithm that returns an <em>approximation</em> of the true edit distance. I am not sure whether this algorithm can produce the edit sequence.</p>

CC BY-SA 4.0
2021-03-19T11:35:12.320Z
2024-03-30T00:00:02.847Z
2024-03-30T00:00:02.847Z
Yossi Gil
<p>If by &quot;edit operations&quot; you mean single character insertions, deletions, and substitutions then I believe a greedy algorithm works.</p>
<p>Let <span class="math-container">$x_i$</span> be the number of ] minus the number of [ in the first <span class="math-container">$i$</span> characters. Every edit operation changes each <span class="math-container">$x_i$</span> by at most 2. Hence you will need at least <span class="math-container">$\lceil \frac {\max x_i} 2 \rceil$</span> 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.</p>
<p>Finally, you need <span class="math-container">$x_n$</span> to be 0. The above operations will reduce <span class="math-container">$x_n$</span> by <span class="math-container">$\max x_i$</span> and this is unavoidable, since an operation at position <span class="math-container">$i$</span> affects exactly those positions after <span class="math-container">$i$</span> and by an equal amount. Hence you will need a final <span class="math-container">$\lceil \frac {\max x_i - x_n} 2 \rceil$</span> 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.</p>
<p>Since the solution is so simple, I doubt there's any literature on it.</p>

CC BY-SA 4.0
2021-03-10T16:58:06.340Z
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?
Yossi Gil
CC BY-SA 4.0
2021-03-11T10:39:14.027Z
$\max x_i$ and $\max x_i - x_n$ are always nonnegative so yes.
Whosyourjay
CC BY-SA 4.0
2021-03-09T11:56:07.813Z
2021-03-09T11:56:07.813Z
Whosyourjay
<p>Given a word <span class="math-container">$w$</span> over <span class="math-container">$\{ [, ] \}$</span>, the alphabet of the two square brackets, the Dyck correction problem is to find the shortest sequence of edit operations that would make <span class="math-container">$w$</span> a Dyck word, i.e., a word in which the squared brackets are balanced.</p>
<p>I can imagine a few practical applications, but my bibliography search yielded nothing. It looks like dynamic programming though. Any ideas?</p>

CC BY-SA 4.0
2021-03-06T19:15:51.017Z
Check: https://arxiv.org/pdf/1904.08402.pdf
Bartosz Bednarczyk
CC BY-SA 4.0
2021-03-12T11:38:01.380Z
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?
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2021-03-12T22:03:03.857Z
Or maybe even something easier: what about visibly pushdown languages?
Bartosz Bednarczyk
CC BY-SA 4.0
2021-03-12T22:07:44.930Z
Btw, might be related: https://arxiv.org/pdf/1504.08259
Bartosz Bednarczyk
<ds.algorithms><dynamic-programming><string-matching>
The Dyck Language Correction Problem
Yossi Gil
# The Dyck Language Correction Problem

(Asked by: username_0 on 2021-03-06)

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?

**Tags:** ds.algorithms, dynamic-programming, string-matching
> **Comments:**
> **username_1**: Check: https://arxiv.org/pdf/1904.08402.pdf  
> **username_2**: 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?  
> **username_1**: Or maybe even something easier: what about visibly pushdown languages?  
> **username_1**: Btw, might be related: https://arxiv.org/pdf/1504.08259  

---

## 2 answers

### Answer by username_0 on 2021-03-19. Score: 6

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.


---

### Answer by username_3 on 2021-03-09. Score: 3

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.

> **Comments:**
> **username_0**: 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?  
> **username_3**: $\max x_i$ and $\max x_i - x_n$ are always nonnegative so yes.  

---

