Asynchronous traces and open petri nets

The relation between process calculi and Petri nets, two fundamental models of concurrency, has been widely investigated. Many proposals exist for encoding process calculi into Petri nets while preserving some behavioural features of interest. We recently introduced a framework where a net encoding can be defined uniformly for calculi with different communication patterns, including synchronous two-party, multiparty, and asynchronous communication. The encoding preserves and reflects several behavioural semantics, notably bisimulation equivalence. The situation is less immediate for asynchronous calculi and trace semantics: considering traces that arise when viewing asynchronous calculi as a fragment of the synchronous ones, trace equivalence is not reflected by the encoding. Focusing on CCS, we argue that this phenomenon is related to the imperfect match between trace inclusion and may testing preorder. We consider an alternative labelled transition systems where the latter issue is solved, and we show that, indeed, the corresponding trace semantics is preserved and reflected by the net encoding.