Paper Details

Regular Sets of Pomsets with Autoconcurrency
Jean Fanchon and Remi Morin

Partially ordered multisets (or pomsets) constitute one of the most basic models of concurrency. We introduce and compare several notions of regularity for pomset languages by means of contexts and residus of different kinds. We establish some interesting closure properties that allow us to relate this approach to SP-recognizability in the particular case of serie-parallel pomsets. Finally we introduce the framework of compatible languages which generalizes several classical formalisms (including generalized trace languages, message sequence charts and firing pomsets of Petri nets). In this way, we identify regular sets of pomsets as recognizable subsets in the monoid of multiset sequences.