THE POSET OF INFINITARY TRACES

Partially commutative monoids, also called trace monoids, are among th e most-studied formalisms to describe the behaviour of distributed sys tems. In order to model systems which never stop, we have to consider an extension of traces, namely infinite traces. Finite-trace monoids a re strongly related to partial-order sets (PoSets), domains and event structures, which are other models to describe the behaviour of distri buted systems. The aim of this paper is to establish similar connexion s between infinite-trace monoids, PoSets and event structures. We prov e that the set of finite and infinite traces with the prefix order is a Scott domain and a coherently complete prime algebraic PoSet. Moreov er, we establish a representation theorem between the class of finite- and infinite-trace PoSets and a subclass of labelled prime event stru ctures.