Given two pictures p and f, p is f-free if f is not a sub-picture of p. A binary picture f is good if for any pair of f-free pictures p and q there exists a bit-to-bit transformation from p to q such that any picture in the intermediate steps is f-free. Such transformation is called f-free transformation. A binary picture is bad if it is not good. These notions generalize to pictures the corresponding ones for strings. We study some properties of bad binary pictures in terms of overlaps and give some examples. Furthermore, we discuss the properties of an index of a bad picture f, that is a minimal picture size (h, k) for which two pictures of such size do not admit a f-free transformation.

Bad Pictures: Some Structural Properties Related to Overlaps

Madonia M.;
2020-01-01

Abstract

Given two pictures p and f, p is f-free if f is not a sub-picture of p. A binary picture f is good if for any pair of f-free pictures p and q there exists a bit-to-bit transformation from p to q such that any picture in the intermediate steps is f-free. Such transformation is called f-free transformation. A binary picture is bad if it is not good. These notions generalize to pictures the corresponding ones for strings. We study some properties of bad binary pictures in terms of overlaps and give some examples. Furthermore, we discuss the properties of an index of a bad picture f, that is a minimal picture size (h, k) for which two pictures of such size do not admit a f-free transformation.
978-3-030-62535-1
978-3-030-62536-8
Bad pictures
Index
Overlap
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/20.500.11769/492233
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact