For the most recent entries see the Petri Nets Newsletter.

Trade-offs in True Concurrency: Pomsets and Mazurkiewicz Traces.

Bloom, B.; Kwiatkowska, M.

In: Mathematical Foundations of Programming Semantics, 7th International Conference Pittsburgh, USA, March 1991, Proceedings, Springer-Verlag. 1993.

Abstract: We compare finite pomsets and Mazurkiewicz traces, two models of true concurrency which generalize strings. We show that Mazurkiewicz traces are equivalent to a restricted class of pomsets. The restrictions lead to more algebraic structure satisfying additional properties. For example, traces are consistently complete in the prefix order, while pomsets are not; also, traces can be distinguished by observing sequences of actions, in contrast to the elaborate scheme required for distinguishing pomsets. Finally, we discuss the operations of sequential and parallel composition in the two models. This is part of an ongoing effort to relate models of concurrency.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography