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. © 2016 Elsevier B.V
Two-dimensional Comma-free and Cylindric Codes
MADONIA, Maria Serafina
2017-01-01
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. © 2016 Elsevier B.V| File | Dimensione | Formato | |
|---|---|---|---|
|
Twodimensional-commafree-and-cylindric-codes2017Theoretical-Computer-Science.pdf
solo gestori archivio
Tipologia:
Versione Editoriale (PDF)
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.
