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 is proved that in general it is undecidable whether a finite set of picture is a code. The subclass of prefix codes is introduced and it is proved that it is decidable whether a finite set of pictures is a prefix code. Further a polynomial time decoding algorithm for finite prefix codes is given. Maximality and completeness of finite prefix codes are studied.
Anselmo, M., Giammarresi, D., Madonia, M. (2014). Prefix picture codes: A decidable class of two-dimensional codes. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 25(8), 1017-1031 [10.1142/S0129054114400218].
Prefix picture codes: A decidable class of two-dimensional codes
GIAMMARRESI, DORA;
2014-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 is proved that in general it is undecidable whether a finite set of picture is a code. The subclass of prefix codes is introduced and it is proved that it is decidable whether a finite set of pictures is a prefix code. Further a polynomial time decoding algorithm for finite prefix codes is given. Maximality and completeness of finite prefix codes are studied.| File | Dimensione | Formato | |
|---|---|---|---|
|
AGMSpecialIssueDlt2013_submit.pdf
solo utenti autorizzati
Licenza:
Copyright dell'editore
Dimensione
299.5 kB
Formato
Adobe PDF
|
299.5 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.
