Methods for relativizing properties of codes

Jürgensen, Helmut and Kari, Lila and Kopecki, Steffen: Methods for relativizing properties of codes. In: Acta cybernetica, (22) 2. pp. 259-292. (2015)

Cikk, tanulmány, mű

Download (656kB) | Preview


The usual setting for information transmission systems assumes that all words over the source alphabet need to be encoded. The demands on encodings of messages with respect to decodability, error-detection, etc. are thus relative to the whole set of words. In reality, depending on the information source, far fewer messages are transmitted, all belonging to some specific language. Hence the original demands on encodings can be weakened, if only the words in that language are to be considered. This leads one to relativize the properties of encodings or codes to the language at hand. We analyse methods of relativization in this sense. It seems there are four equally convincing notions of relativization. We compare those. Each of them has their own merits for specific code properties. We clarify the differences between the four approaches. We also consider the decidability of relativized properties. If P is a property defining a class of codes and L is a language, one asks, for a given language C, whether C satisfies P relative to L. We show that in the realm of regular languages this question is mostly decidable.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2015
Volume: 22
Number: 2
ISSN: 0324-721X
Page Range: pp. 259-292
Language: angol
Uncontrolled Keywords: Informatika kódolás
Additional Information: Bibliogr.: p. 289-291.
Date Deposited: 2016. Oct. 17. 10:36
Last Modified: 2018. Jun. 06. 18:37

Actions (login required)

View Item View Item