Methods for Relativizing Properties of Codes

The usual setting for information transmission systems assumes that all words over the source alphabet need to be encoded. The de-mands 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 trans-mitted, all belonging to some specific language. Hence the original demands on encodings can be weakened, if only the words in that lan-guage 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 clar-ify 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. 1 Codes in Information Systems In an information system, a source S generates messages1 which, after some modifications, enter a channel K. The channel may change a message be-cause of physical errors or human interference or other reasons. For a give