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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-01656353
Contributor : Hal Ifip <>
Submitted on : Tuesday, December 5, 2017 - 3:42:13 PM
Last modification on : Wednesday, December 6, 2017 - 10:48:12 AM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2020-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Marcella Anselmo, Dora Giammarresi, Maria Madonia. Infinite Two-Dimensional Strong Prefix Codes: Characterization and Properties. 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2017, Milan, Italy. pp.19-31, ⟨10.1007/978-3-319-58631-1_2⟩. ⟨hal-01656353⟩

Share

Metrics

Record views

195