A two-dimensional code is defined as a set of rectangular pictures over an alphabet Σ such that any picture over Σ is tilable in at most one way with pictures in X. It is in general undecidable whether a set of pictures is a code, even in the finite case. Recently, finite strong prefix codes were introduced in [3] as a family of decidable picture codes. In this paper we study infinite strong prefix codes and give a characterization for the maximal ones based on iterated extensions. Moreover, we prove some properties regarding the measure of these codes.

Anselmo, M., Giammarresi, D., & Madonia, M. (2017). Infinite two-dimensional strong prefix codes: Characterization and properties. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.19-31). Springer Verlag [10.1007/978-3-319-58631-1_2].

Infinite two-dimensional strong prefix codes: Characterization and properties

Giammarresi, Dora
;
2017

Abstract

A two-dimensional code is defined as a set of rectangular pictures over an alphabet Σ such that any picture over Σ is tilable in at most one way with pictures in X. It is in general undecidable whether a set of pictures is a code, even in the finite case. Recently, finite strong prefix codes were introduced in [3] as a family of decidable picture codes. In this paper we study infinite strong prefix codes and give a characterization for the maximal ones based on iterated extensions. Moreover, we prove some properties regarding the measure of these codes.
23rd IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems, AUTOMATA 2017
ita
2017
Dipartimento di Informatica, Sistemistica e Comunicazione
Rilevanza internazionale
contributo
Settore INF/01 - Informatica
English
Measure; Prefix codes; Two-dimensional languages; Theoretical Computer Science; Computer Science (all)
http://springerlink.com/content/0302-9743/copyright/2005/
Intervento a convegno
Anselmo, M., Giammarresi, D., & Madonia, M. (2017). Infinite two-dimensional strong prefix codes: Characterization and properties. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp.19-31). Springer Verlag [10.1007/978-3-319-58631-1_2].
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: http://hdl.handle.net/2108/196848
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact