On compressing interchange classes of events in a concurrent system

The use of strings is standard in modeling the temporal ordering of events in a sequence computation. A recent prize-winning paper in the computer architecture literature applies a grammar-based lossless data compression algorithm to the sequence of events that transpire while a computer program runs and utilizes the resulting grammar to better understand the program´s dynamic behavior and improve its performance. Lossless data compression is most suitable for this purpose then there is a well-defined total ordering of event occurrences. In concurrent systems, i.e., systems involving multiple processes, there is a partial ordering of events. Trace theory employs congruence or interchange classes of words over partially commutative alphabets as a way to generalize strings to executions of concurrent processes. Universal compression schemes for a rate distortion problem in which the goal is to reproduce a string, which is equivalent to the original string are considered, and it is shown that for a large collection of dependence alphabets, interchange entropy, i.e., the rate distortion limit can be attained asymptotically.