A two-dimensional code of pictures is defined as a set X⊆Σ⁎⁎ such that any picture over Σ is tilable in at most one way with pictures in X. It has been proved that it is undecidable whether a finite set of pictures is a code. Here we introduce two classes of picture codes: the comma-free codes and the cylindric codes, with the aim of generalizing the definitions of comma-free (or self-synchronizing) code and circular code of strings. The properties of these classes are studied and compared, in particular in relation to maximality and completeness. As a byproduct, we introduce self-covering pictures and study their periodicity issues.
Two-dimensional comma-free and cylindric codes
ANSELMO, Marcella;
2017
Abstract
A two-dimensional code of pictures is defined as a set X⊆Σ⁎⁎ such that any picture over Σ is tilable in at most one way with pictures in X. It has been proved that it is undecidable whether a finite set of pictures is a code. Here we introduce two classes of picture codes: the comma-free codes and the cylindric codes, with the aim of generalizing the definitions of comma-free (or self-synchronizing) code and circular code of strings. The properties of these classes are studied and compared, in particular in relation to maximality and completeness. As a byproduct, we introduce self-covering pictures and study their periodicity issues.| File | Dimensione | Formato | |
|---|---|---|---|
|
1-s2.0-S0304397516302523-main.pdf
accesso aperto
Tipologia:
Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza:
Creative commons
Dimensione
507.98 kB
Formato
Adobe PDF
|
507.98 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
