Infinite Two-Dimensional Strong Prefix Codes: Characterization and Properties

Abstract : A two-dimensional code is defined as a set of rectangular pictures over an alphabet $\varSigma $ such that any picture over $\varSigma $ 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.
Type de document :
Communication dans un congrès
Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.19-31, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_2〉
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01656353
Contributeur : Hal Ifip <>
Soumis le : mardi 5 décembre 2017 - 15:42:13
Dernière modification le : mercredi 6 décembre 2017 - 10:48:12

Fichier

 Accès restreint
Fichier visible le : 2020-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Marcella Anselmo, Dora Giammarresi, Maria Madonia. Infinite Two-Dimensional Strong Prefix Codes: Characterization and Properties. Alberto Dennunzio; Enrico Formenti; Luca Manzoni; Antonio E. Porreca. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. Springer International Publishing, Lecture Notes in Computer Science, LNCS-10248, pp.19-31, 2017, Cellular Automata and Discrete Complex Systems. 〈10.1007/978-3-319-58631-1_2〉. 〈hal-01656353〉

Partager

Métriques

Consultations de la notice

102