Remarks on the equivalence of c-e structures and Petri nets (Q1209978)

Cause-effect structures (c-e structures) were introduced by L. Czaja in the late eighties. These structures resemble (place/transition) Petri nets very closely. They have places, but transitions are only implicitly present -- they are ``hidden'' in cause-effect dependencies among places descripted by formal polynomials (``+'' being a free-choice operator, ``\(*\)'' a parallel one). The ``hidden'' transitions are called firing components in the paper. Every c-e structure has its strongly equivalent counterpart among Petri nets -- there are bijections between the sets of places and the sets of transitions (firing components) preserving pre- and postsets. The author proves that the opposite is not true (thus correcting a mistake of Czaja) by showing a Petri net which does not have a strongly equivalent c-e structure. The main result shows that for any Petri net a (not strongly) equivalent c-e structure can be constructed; instead of a bijection between the sets of places, only a bijection between the sets of equivalence classes of places suffices (two places are equivalent if their pre- and postsets are equal).