Reducing
k-Safe Petri Nets to Pomset-Equivalent 1-Safe Petri Nets
Eike Best6 and Harro Wimmel7
| (6) |
Carl von Ossietzky Universität Oldenburg, D-26111 Oldenburg |
| (7) |
Universität Koblenz-Landau, D-56075 Koblenz |
Abstract
It is a well-known fact that for every k-safe Petri net, i.e. a Petri net in which no place contains more than k ∈ ℕ tokens under any reachable marking, there is a 1-safe Petri net with the same interleaving behaviour. Indeed these types
of Petri nets generate regular languages. In this paper, we show that this equivalence of k-safe and 1-safe Petri nets holds also for their pomset languages, a true-concurrency semantics.
Keywords Causality / partial order theory of concurrency - Petri nets - Pomsets
References secured to subscribers.