Compressing a Representation of Events in a Concurrent System
25 June 2003
Network information theory traditionally studies communication problems involving many senders and receivers. Using different connotations of the word "network" we begin to explore an alternate type of network information theory problem which may be viewed as being in the realm of semantic information theory. This rate distortion problem is motivated by work in computer science in the areas of concurrency, program profiling, and compression of executable code, and leads to a new generalization of Kolmogorov complexity and a new graph entropy called the interchange entropy. We provide some of the basic properties of the interchange entropy.