The Information Rate of Asynchronous Sources
Samy Abbes · 2006
We describe from an information-theoretic point of view asynchronous sources of informations. Models for such sources are found in the literature irn Mathematics and irn Computer science. In particular, trace morioids and Petri nets are models for asynchronous systems. The runs of a system with a Petri net-like model do not distirnguish between the different inter-leavings of concurrent actions, which is the main feature of these models. Conrsiderirng different probabilistic settings for these models-namely, random walks on monroids and so-called Markov nets-we study their entropy rate. We define by this way the capacity of a trace monoid, which is the largest amount of information that can be encoded from a synchronous to an asynchronous source. A connection with Markov processes on Directed Complete Partial Orders is established, spanning a bridge with domain theory.