Remarks on the equivalence of c-e structures and Petri nets
type: Item
instance of: scholarly article
title: Remarks on the equivalence of c-e structures and Petri nets
zbMATH Open document ID: 0792.68122
DOI: 10.1016/0020-0190(93)90114-O
author: Marek Raczunas
published in: Information Processing Letters
publication date: 1993-05-16T00:00:00Z
review text: 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).
Mathematics Subject Classification ID: 68Q85
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 168858
zbMATH Keywords: cause-effect structure
zbMATH Keywords: Petri nets
reviewed by: Petr Jančar
MaRDI profile type: Publication
cites work: Cause-effect structures
cites work: Finite processes in cause-effect structures and their composition
cites work: Propositional description of finite cause-effect structures
description: scientific article; zbMATH DE number 168858