Making Petri Nets Safe and Free of Internal Transitions

Issue title: Half a Century of Inspirational Research: Honoring the Scientific Influence of Antoni Mazurkiewicz

Article type: Research Article

Authors: Best, Eike | Darondeau, Philippe | Wimmel, Harro

Affiliations: Parallel Systems, Department of Computing Science, Carl von Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany. E-mail: [email protected] | IRISA, campus de Beaulieu, F-35042 Rennes Cedex, France. E-mail: [email protected] | Parallel Systems, Department of Computing Science, Carl von Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany. E-mail: [email protected]

Abstract: This paper discusses the following results: that bounded Petri nets can be transformed into pomset-equivalent safe nets; that boundedmarked graphs can be transformed into step-language-equivalent safe marked graphs; that safe labelled marked graphs can be transformed into τ–free safe labelled marked graphs; and that marked graphs can be separated. The paper also lists some open problems that have arisen in this context.

Journal: Fundamenta Informaticae, vol. 80, no. 1-3, pp. 75-90, 2007