Abstract :
A binary sequence satisfies a one-dimensional (d, k) runlength constraint if every run of zeroes has length at least d and at most k. A binary sequence satisfies a one-dimensional (d1, k1, d2, k2) runlength constraint if every run of zeroes has length at least d1 and at most k2 and every run of ones has length at least d2 and at most k2. A two-dimensional binary array is said to satisfy a (d1, k1, d2, k2; d 3, d4, k4) runlength constraint if it satisfies the one-dimensional (d1, k1, d2 , k2) runlength constraint horizontally (i.e. on every row) and the one-dimensional (d3, k3, d4, k4) runlength constraint vertically (i.e. on every column). For convenience, we will say that a binary array satisfies the (d,k) runlength constraint if each row and each column satisfy the (d,k) runlength constraint and that a binary array satisfies the (d1, k1, d2, k2) runlength constraint if it is (d1, k1, d2 , k2) runlength constrained both horizontally and vertically. We say that a binary array satisfies the (d1, k 1; d3, k3) runlength constraint if each row satisfies the (d1, k1, d1, k1 ) runlength constraint and each column satisfies the (d3, k3, d3, k3) runlength constraint. Finally, we always allow violation of the smallest runlength constraint at the beginning and the end sequences and at the edges of arrays. In this work we examine the following basic question: for which values of d1, k1, d2, k2, d 3, k3, d4, k4, is C(d1 , k1, d2, k2; d3, k 3, d4, k4) positive and for which values is it equal to zero?
