The complexity of Petri Net transformations
Loading...
Authors
Donaldson, SR
Bause, F
Kritzinger, Pieter S.
Issue Date
1996
Type
Article
Language
en
Keywords
Petri Nets , Analysis of Algorithms , Problem complexity , Program verification , Model validation and analysis , Model development , Reduction and synthesis transformations , Liveness , Boundedness
Alternative Title
Abstract
We consider the complexity of several property preserving Petri net transformations found in the literature. These transforÂmations were candidates for.inclusion in a software tool to peiform liveness and boundedness analysis on Petri nets. These results show that it is infeasible for certain transformations in general to assist in liveness and boundedness analysis. We also consider synthesis transformations and show, for each transformation, their complexities. In each case, we consider the complexity of the decision problem with regard to the applicability of the transformation.
.
Description
Citation
Donaldson SR, Bause F & Kritzinger PS (1996) The complexity of Petri Net transformations. South African Computer Journal, Number 18, 1996
Publisher
South African Computer Society (SAICSIT)
License
Journal
Volume
Issue
PubMed ID
DOI
ISSN
2313-7835