Concurrent Processes and the Interchange Entropy

Concurrency is a fundamental concept in computer science which is concerned with the study of systems involving multiple processes. The order of events in such a system is unpredictable because of the independence of events occurring in the individual processes. Trace theory is a successful model for the execution of concurrent processes which employs congruence classes of words over partially commutative alphabets. These congruence or interchange classes generalize the more familiar notions of strings and type classes. We consider a rate distortion problem in which the objective is to reproduce a string which is equivalent to the original string. This leads to a new graph entropy called the interchange entropy, and we provide some of its basic properties.