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.
2017
978-3-319-60251-6
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11386/4687784
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 2
social impact