A picture is a two-dimensional counterpart of a string and it is represented by a rectangular array of symbols over a finite alphabet Σ. A set X of pictures over Σ is a code if every picture over Σ is tilable in at most one way with pictures in X. Recently, the definition of strong prefix code was introduced as a decidable family of picture codes, and a construction procedure for maximal strong prefix (MSP) codes was proposed. Unfortunately, the notion of completeness cannot be directly transposed from strings to pictures without loosing important properties. We generalize to pictures a special property satisfied by complete set of strings that allow to prove interesting characterization results for MSP codes. Moreover, we show an encoding algorithm for pictures using pictures from a MSP code. The algorithm is based on a new data structure for the representation of MSP codes.

Anselmo, M., Giammarresi, D., Madonia, M. (2018). Encoding pictures with maximal codes of pictures. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.552-565). Springer Verlag [10.1007/978-3-319-73117-9_39].

Encoding pictures with maximal codes of pictures

Giammarresi, Dora
;
2018-01-01

Abstract

A picture is a two-dimensional counterpart of a string and it is represented by a rectangular array of symbols over a finite alphabet Σ. A set X of pictures over Σ is a code if every picture over Σ is tilable in at most one way with pictures in X. Recently, the definition of strong prefix code was introduced as a decidable family of picture codes, and a construction procedure for maximal strong prefix (MSP) codes was proposed. Unfortunately, the notion of completeness cannot be directly transposed from strings to pictures without loosing important properties. We generalize to pictures a special property satisfied by complete set of strings that allow to prove interesting characterization results for MSP codes. Moreover, we show an encoding algorithm for pictures using pictures from a MSP code. The algorithm is based on a new data structure for the representation of MSP codes.
44th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2018
aut
2018
Rilevanza internazionale
contributo
2018
Settore INF/01 - INFORMATICA
English
Theoretical Computer Science; Computer Science (all)
http://springerlink.com/content/0302-9743/copyright/2005/
Intervento a convegno
Anselmo, M., Giammarresi, D., Madonia, M. (2018). Encoding pictures with maximal codes of pictures. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.552-565). Springer Verlag [10.1007/978-3-319-73117-9_39].
Anselmo, M; Giammarresi, D; Madonia, M
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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/196843
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact