Sets of Pictures Avoiding Overlaps

A string set avoids overlaps if it has the property that the prefix of each string in the set does not coincide with the suffix of any string in the set. The problem of avoiding overlaps in strings is extensively investigated since it plays 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 one 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 first investigate the problem of generating all unbordered pictures of fixed size. Then, we study particular sets of unbordered pictures that are non-overlapping each others. We show that the frame of the pictures has a special role in defining these sets. In particular, we prove that there exist kinds of synchronization frames that can be put around the pictures of any set to make it non-overlapping. Finally, we present a construction of non-expandable non-overlapping sets of pictures which starts from some property of frame-completeness. The research that led to the present paper was partially supported by a grant of the group GNCS of INdAM .