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-01-01
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
