A set X X ⊆ Σ∗∗ of pictures is a code if every picture over Σ is tilable in at most one way with pictures in X. The definition of strong prefix code is introduced. The family of finite strong prefix codes is decidable and it has a polynomial time decoding algorithm. Maximality for finite strong prefix codes is also studied and related to the notion of completeness. We prove that any finite strong prefix code can be embedded in a unique maximal strong prefix code that has minimal size and cardinality. A complete characterization of the structure of maximal finite strong prefix codes completes the paper.
Anselmo, M., Giammarresi, D., Madonia, M. (2017). Structure and properties of strong prefix codes of pictures. MATHEMATICAL STRUCTURES IN COMPUTER SCIENCE, 27(2), 123-142 [10.1017/S0960129515000043].
Structure and properties of strong prefix codes of pictures
Giammarresi, Dora
;
2017-01-01
Abstract
A set X X ⊆ Σ∗∗ of pictures is a code if every picture over Σ is tilable in at most one way with pictures in X. The definition of strong prefix code is introduced. The family of finite strong prefix codes is decidable and it has a polynomial time decoding algorithm. Maximality for finite strong prefix codes is also studied and related to the notion of completeness. We prove that any finite strong prefix code can be embedded in a unique maximal strong prefix code that has minimal size and cardinality. A complete characterization of the structure of maximal finite strong prefix codes completes the paper.File | Dimensione | Formato | |
---|---|---|---|
MSCS-S0960129515000043a.pdf
solo utenti autorizzati
Tipologia:
Versione Editoriale (PDF)
Licenza:
Copyright dell'editore
Dimensione
349.63 kB
Formato
Adobe PDF
|
349.63 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.