What is the closed formula for the following recurrence relation: A(i,j) = (A(i-1,j) & A(i,j-1))'?

44 Views Asked by At

Here (..)' is the complement and & is the bitwise operator AND.

Consider initial conditions to be 2 binary strings (only 1s and 0s) of length n and m, for all A(0,j): (1 <= j <= m) and A(i,0) : (1 <= i <= n)

I need a closed formula for A(i,j) where 1 <= j <= m , 1 <= i <= n

1

There are 1 best solutions below

2
On BEST ANSWER

Just a long comment:

I don't think your recursion is well-defined. Assume the giving starting arrays are both of length $1$, so we know $A(0,1)$ and $A(1,0)$. Now say I want to compute $A(0,2)$. For that, I would need $A(-1,2)$ and $A(0,1)$, a problem because we don't know what to do for negative $n$. If you don't allow $0$ for $n$, simply take $A(1,2)$, where you get to the problem of computing $A(0,2)$ already after the first step.

Thus, I think that we need to give $A(j,0)$ and $A(i,0)$ for all natural numbers $i$, $j$, not just for a finite interval. So the initial conditions themselves have to be functions (maybe recursive themselves), making this whole thing really complicated.
Or, of course, making it really simply, depending on what the initial conditions are.