A polynomial λ-bisimilar normalization for reset Petri nets

✍ Scribed by Catherine Dufourd; Alain Finkel

• Book ID: 104326657
• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 397 KB
• Volume: 222
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(98)00351-x

✦ Synopsis

Reset Petri nets extend Petri nets by allowing transitions to empty places, in addition to the usual adding or removing of constants. A Reset Petri net is normalized if the flow function over the Petri arcs (labeled with integers) and the initial state are valuated into {0, 1}. In this paper, we give an efficient method to turn a general Reset Petri net into a 2-bisimilar normalized Reset Petri net. Our normalization preserves the main usually studied properties: boundedness, reachability, t-liveness and language (through a 2-labeling function). The main contribution is the improvement of the complexity: our algorithm takes a time in O(size(N)2), for a Reset Petri net N, while other known normalizations require an exponential space and are presented for Petri nets only. (~ 1999 Elsevier Science B.V. All rights reserved.