Encoding pictures with maximal codes of pictures
| Autor: | Maria Madonia, Dora Giammarresi, Marcella Anselmo |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Prefix code Settore INF/01 - Informatica Computer science Two dimensional languages Two dimensional codes Prefix codes String (computer science) Computer Science (all) 0102 computer and information sciences 02 engineering and technology Theoretical Computer Science Characterization (mathematics) 01 natural sciences Prefix Set (abstract data type) 010201 computation theory & mathematics Completeness (order theory) 0202 electrical engineering electronic engineering information engineering Code (cryptography) 020201 artificial intelligence & image processing |
| Zdroj: | SOFSEM 2018: Theory and Practice of Computer Science ISBN: 9783319731162 SOFSEM |
| Popis: | A picture is a two-dimensional counterpart of a string and it is represented by a rectangular array of symbols over a finite alphabet \(\varSigma \). A set X of pictures over \(\varSigma \) is a code if every picture over \(\varSigma \) is tilable in at most one way with pictures in X. Recently, the definition of strong prefix code was introduced as a decidable family of picture codes, and a construction procedure for maximal strong prefix (MSP) codes was proposed. Unfortunately, the notion of completeness cannot be directly transposed from strings to pictures without loosing important properties. We generalize to pictures a special property satisfied by complete set of strings that allow to prove interesting characterization results for MSP codes. Moreover, we show an encoding algorithm for pictures using pictures from a MSP code. The algorithm is based on a new data structure for the representation of MSP codes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|