Dynamic Programming on bracketed sequences

Question

I am currently working on the following problem that involves developing a dynamic programming algorithm for finding the length of the shortest fully bracketed expression (FBE), $y$ that contains a given string $x = x_1x_2...x_n$. An FBE is defined as a string over the characters (,),[, and ] that is either

1. the empty string
2. the string $[T]$ or $(T)$, where $T$ is a fully bracketed expression, or
3. the string $TU$, where $T$ and $U$ are fully bracketed expressions.

So far I have worked through the potential recursive function $T(i,j)$ which I've defined as the length of the shortest possible FBE that contains $x_i...x_j$ as a subsequence (not necessarily a string). And I know that in the shortest FBE containing $x_i...x_j$ that $x_i$ is either "mathced" to an appropriate character $x_k$ such that $i + 1 \leq k \leq j$, or it isn't. So I think that I need two cases; either the former is true, or the latter is true.

I'm having trouble formalizing this and creating a recursion. I'm not sure how to deal with the addition of characters. Any help would be appreciated! Thanks!

Answer 1

Let $S(i,j)$ be the set of the shortest FBEs containing $x_i\ldots x_j$. We focus on non-trivial cases ($j-i\ge 2$).

If there is an element in $S(i,j)$ with the form $AB$ where neither $A$ nor $B$ is empty, there must exist $i\le k<j$ such that $x_i,\ldots, x_k$ belong to $A$ and $x_{k+1},\ldots,x_j$ belongs to $B$. Easy to see $T(i,j)=\min_k\{T(i,k)+T(k+1,j)\}$.

Otherwise, take an element from $S(i,j)$. Assume WLOG it has the form [$A$]. Note $x_{i+1},\ldots,x_{j-1}$ are contained in $A$, we have $T(i,j)\ge T(i+1,j-1)+2$. Furthermore, if either $x_i\neq$ [ or $x_j\neq$ ] (say $x_i\neq$ [ WLOG), then $A$[] (with the form $AB$) is also an FBE containing $x_i\ldots x_j$, which contradicts to the assumption. Hence $x_i$ and $x_j$ must match.

Combining the two paragraphs above, we have proved

• if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

• if $x_i$ and $x_j$ match,

$$T(i,j)\ge \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

Note concentrating a shortest FBE containing $x_i\ldots x_k$ and a shortest FBE containing $x_{k+1}\ldots x_j$ constitutes an FBE containing $x_i\ldots x_j$, so $T(i,j)\le \min_k\{T(i,k)+T(k+1,j)\}$. In addition, if $x_i$ and $x_j$ match, say $x_i=$ [ and $x_j=$ ], and let $s$ be a shortest FBE containing $x_{i+1}\ldots x_{j-1}$, then [$s$] is an FBE containing $x_i\ldots x_j$, so $T(i,j)\le T(i+1,j-1)+2$. As a conclusion, if $x_i$ and $x_j$ match,

$$T(i,j)\le \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$

So the recursion turns out to be

• if $x_i$ and $x_j$ do not match,

$$T(i,j)= \min_k\{T(i,k)+T(k+1,j)\},$$

• if $x_i$ and $x_j$ match,

$$T(i,j)= \min\left\{\min_k\{T(i,k)+T(k+1,j)\}, T(i+1,j-1)+2\right\}.$$