In: L. Brim, P. Jancar, M. Kretínský, A. Kucera (Eds.): CONCUR 2002 - Concurrency Theory, 13th International Conference, Brno, Czech Republic, August 20-23, 2002, pages 1-402pp. Springer Verlag, LNCS 2421, September 2002.
Abstract: 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 residues of different kinds. We establish some interesting closure properties that allow us to relate this approach to SP-recognizability in the particular case of series-parallel pomsets. Finally we introduce the framework of compatible languages which generalizes several classical formalisms (including 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.