In string combinatorics, the sets of strings that have no over- laps (i.e. the prex of one string does not coincide with the suffix of an- other 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 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 bix-free) string. We study the problem of generating all unbordered pictures of xed size and present a construction of non-expandable non-overlapping sets of pictures together with some examples.
Avoiding Overlaps in Pictures
ANSELMO, Marcella;
2017-01-01
Abstract
In string combinatorics, the sets of strings that have no over- laps (i.e. the prex of one string does not coincide with the suffix of an- other 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 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 bix-free) string. We study the problem of generating all unbordered pictures of xed size and present a construction of non-expandable non-overlapping sets of pictures together with some examples.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.