10.37
Idea: treat every binary entry of the multiplication table as a production rule of a context–free grammar and run the standard CYK-style dynamic programme.
Let Σ = {1,…,k} be the symbols, the input string x = x1…xn, the table entry table[p][q] = r, and the desired value a.
Algorithm (DP over substrings):
T[i][j] ⊆ Σ // 1 ≤ i ≤ j ≤ n
for i = 1 … n: // substrings of length 1
T[i][i] = { x_i }
for len = 2 … n: // increasing length
for i = 1 … n−len+1:
j = i+len−1
T[i][j] = ∅
for m = i … j−1: // split position
for p ∈ T[i][m]:
for q ∈ T[m+1][j]:
r = table[p][q]
T[i][j] ← T[i][j] ∪ {r}
return (a ∈ T[1][n])
Explanation:
• T[i][j] stores every symbol that can be produced by some parenthesisation of the substring xi…xj.
• The outer two loops enumerate O(n²) substrings, the inner split loop O(n) positions; for every split at most k² table look-ups are performed.
• Total time complexity O(n³·k²), space O(n²·k). Both are polynomial in n and k.
• If the goal symbol a ends up in T[1][n] we have found at least one valid parenthesisation; otherwise none exists.
The same DP can be augmented to reconstruct an actual parenthesisation by remembering, for each entry inserted into T[i][j], the split point m and the pair (p,q) that produced it, then back-tracing from (1,n,a).
Back to
Chapter 10
