The Information Rate of Asynchronous Sources

摘要

We describe from an information-theoretic point of view asynchronous sources of informations. Models for such sources are found in the literature in mathematics and in computer science. In particular, trace monoids and Petri nets are models for asynchronous systems. The runs of a system with a Petri net-like model do not distinguish between the different inter-leavings of concurrent actions, which is the main feature of these models. Considering different probabilistic settings for these models - namely, random walks on monoids 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