Avoiding Overlaps in Pictures

Pictures are a generalization of strings to two dimensions and they are represented by two-dimensional (rectangular) arrays of symbols taken from a finite alphabet $\Sigma$.

Extending results from the formal string language theory to two dimensions is a very challenging task. The two-dimensional structure in fact imposes some intrinsic difficulties even in the basic concepts. For example, the definition of “prefix” of a string can be extended to a picture by considering its rectangular portion in the top-left corner; nevertheless, if one deletes a prefix from a picture, the remaining part is not a picture anymore.

In string combinatorics, strings that have no overlaps (i.e. the prefix of one string does not coincide with the suffix of another string) are extensively investigated since they play an important role in the context of string matching and coding. The notion of overlap can be extended naturally to two dimensions; two pictures $p$ and $q$ have an overlap if one can put the top-left corner of $p$ on some position in $q$ in such a way that all symbols in the common positions coincide. A picture with no self-overlaps is called unbordered and it is a generalization in two dimensions of an unbordered (or bifix-free) string.

We present a construction of non-expandable non-overlapping sets of pictures. Many examples of applications are shown.

Joint work with Marcella Anselmo and Maria Madonia.