Summary: The Polish scientist L. Czaja has proposed an original net model, the so-called cause-effect structure (CES) The cause-effect structure is similar to Petri nets (PN), but differs by the following features: CES have only one type of nodes, which correspond to places in PN: the role of transitions is fulfilled by certain substructures, which are not defined explicitly and are derivable from the system of node interconnections; node interconnections are incorporated in two “indices” assigned to each node; they represent collections of node subsets, so that the upper “index” denotes groups of (alternative) predecessors of the given node and the lower “index” groups of successors of the given node.
In a subsequent study, L. Czaja [Minimal/maximal time for cause-effect structures, Humboldt Univ. Berlin, F. B. Informatik (June 1993)] expanded the CES by introducing two different concepts of time. Czaja’s first time model – minimum delay time – corresponds in PN to the model proposed by J. Sifakis [Performance evaluation of systems using nets, Lect. Notes Comput. Sci. 84 (1980)]; Czaja’s second time model – maximum activity time – does not have direct analogues in PN. It is closest to Merlin’s model [P. M. Merlin and D. J. Farber, IEEE Trans. Commun. COM-24, 1036-1043 (1976; Zbl 0362.68096)] (has the same modeling capabilities when combined with the first model), but is much simpler for net analysis and verification due to its discrete-time nature.
Interesting questions arise: what is the relationship between CES and PN, and how do Czaja’s time models “superimpose” on PN?
M. Raczunas [Inf. Process. Lett. 45, No. 4, 165-169 (1993; Zbl 0792.68122)] asserts that a strictly equivalent PN exist for each CES. It still remains, however, to consider the mapping of timed CES into timed PN and to examine the resulting increase of model complexity.
We propose an algorithm that maps CES into PN. This algorithm is easily modified to the timed case. Unlike the approach of Raczunas, who has focused on the excessively strong concept of structural equivalence, we consider merely behavioral equivalence of CES and PN. Under this approach, the initial marking of the PN (the initial state of the CES) is an essential element of the system (contrary to its role in the structural equivalence approach), because two PNs may be equivalent with one initial marking and not with another initial marking.
An important part of the proposed algorithm is the construction of the set of CES enabled components. Enabled components play an important role in the operation of the system, but are not defined explicitly in CES. It is this part of the algorithm that increases the complexity of the model.
In conclusion, we demonstrate the algorithm in application to a one-bit protocol.