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.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - Informatica
English
Two-dimensional languages; codes; prefix codes; maximality; completeness
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].
Anselmo, M; Giammarresi, D; Madonia, M
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
AGMSpecialIssueDlt2013_submit.pdf

accesso solo dalla rete interna

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.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2108/122477
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 15
  • ???jsp.display-item.citation.isi??? 12
social impact