Infinite Two-dimensional Strong Prefix Codes: characterization and properties
| Autor: | Dora Giammarresi, Marcella Anselmo, Maria Madonia |
|---|---|
| Přispěvatelé: | Università degli Studi di Salerno (UNISA), Università degli Studi di Roma Tor Vergata [Roma], Università degli studi di Catania [Catania], Alberto Dennunzio, Enrico Formenti, Luca Manzoni, Antonio E. Porreca, TC 1, WG 1.5 |
| Rok vydání: | 2017 |
| Předmět: |
Prefix code
Block code Discrete mathematics Settore INF/01 - Informatica Computer science Computer Science (all) Two-dimensional languages Measure Prefix codes Theoretical Computer Science 020207 software engineering 0102 computer and information sciences 02 engineering and technology Prefix grammar Kraft's inequality 01 natural sciences Measure (mathematics) Decidability Prefix 010201 computation theory & mathematics Iterated function 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Cellular Automata and Discrete Complex Systems ISBN: 9783319586304 AUTOMATA Lecture Notes in Computer Science 23th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA) 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⟩ |
| Popis: | Part 2: Regular Papers; International audience; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|