The complexity of Petri net transformations

Simple item page
dc.contributor.advisorKritzinger, Pieter Sen_ZA
dc.contributor.authorDonaldson, Stephen Richarden_ZA
dc.date.accessioned2015-12-28T06:11:39Z
dc.date.available2015-12-28T06:11:39Z
dc.date.issued1993en_ZA
dc.descriptionBibliography: pages 124-127.en_ZA
dc.description.abstractThis study investigates the complexity of various reduction and synthesis Petri net transformations. Transformations that preserve liveness and boundedness are considered. Liveness and boundedness are possibly the two most important properties in the analysis of Petri nets. Unfortunately, although decidable, determining such properties is intractable in the general Petri net. The thesis shows that the complexity of these properties imposes limitations on the power of any reduction transformations to solve the problems of liveness and boundedness. Reduction transformations and synthesis transformations from the literature are analysed from an algorithmic point of view and their complexity established. Many problems regarding the applicability of the transformations are shown to be intractable. For reduction transformations this confirms the limitations of such transformations on the general Petri net. The thesis suggests that synthesis transformations may enjoy better success than reduction transformations, and because of problems establishing suitable goals, synthesis transformations are best suited to interactive environments. The complexity of complete reducibility, by reduction transformation, of certain classes of Petri nets, as proposed in the literature, is also investigated in this thesis. It is concluded that these transformations are tractable and that reduction transformation theory can provide insight into the analysis of liveness and boundedness problems, particularly in subclasses of Petri nets.en_ZA
dc.identifier.apacitationDonaldson, S. R. (1993). <i>The complexity of Petri net transformations</i>. (Thesis). University of Cape Town ,Faculty of Science ,Department of Computer Science. Retrieved from http://hdl.handle.net/11427/16009en_ZA
dc.identifier.chicagocitationDonaldson, Stephen Richard. <i>"The complexity of Petri net transformations."</i> Thesis., University of Cape Town ,Faculty of Science ,Department of Computer Science, 1993. http://hdl.handle.net/11427/16009en_ZA
dc.identifier.citationDonaldson, S. 1993. The complexity of Petri net transformations. University of Cape Town.en_ZA
dc.identifier.ris TY - Thesis / Dissertation AU - Donaldson, Stephen Richard AB - This study investigates the complexity of various reduction and synthesis Petri net transformations. Transformations that preserve liveness and boundedness are considered. Liveness and boundedness are possibly the two most important properties in the analysis of Petri nets. Unfortunately, although decidable, determining such properties is intractable in the general Petri net. The thesis shows that the complexity of these properties imposes limitations on the power of any reduction transformations to solve the problems of liveness and boundedness. Reduction transformations and synthesis transformations from the literature are analysed from an algorithmic point of view and their complexity established. Many problems regarding the applicability of the transformations are shown to be intractable. For reduction transformations this confirms the limitations of such transformations on the general Petri net. The thesis suggests that synthesis transformations may enjoy better success than reduction transformations, and because of problems establishing suitable goals, synthesis transformations are best suited to interactive environments. The complexity of complete reducibility, by reduction transformation, of certain classes of Petri nets, as proposed in the literature, is also investigated in this thesis. It is concluded that these transformations are tractable and that reduction transformation theory can provide insight into the analysis of liveness and boundedness problems, particularly in subclasses of Petri nets. DA - 1993 DB - OpenUCT DP - University of Cape Town LK - https://open.uct.ac.za PB - University of Cape Town PY - 1993 T1 - The complexity of Petri net transformations TI - The complexity of Petri net transformations UR - http://hdl.handle.net/11427/16009 ER - en_ZA
dc.identifier.urihttp://hdl.handle.net/11427/16009
dc.identifier.vancouvercitationDonaldson SR. The complexity of Petri net transformations. [Thesis]. University of Cape Town ,Faculty of Science ,Department of Computer Science, 1993 [cited yyyy month dd]. Available from: http://hdl.handle.net/11427/16009en_ZA
dc.language.isoengen_ZA
dc.publisher.departmentDepartment of Computer Scienceen_ZA
dc.publisher.facultyFaculty of Scienceen_ZA
dc.publisher.institutionUniversity of Cape Town
dc.subject.otherComputer Scienceen_ZA
dc.titleThe complexity of Petri net transformationsen_ZA
dc.typeMaster Thesis
dc.type.qualificationlevelMasters
dc.type.qualificationnameMScen_ZA
uct.type.filetypeText
uct.type.filetypeImage
uct.type.publicationResearchen_ZA
uct.type.resourceThesisen_ZA
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
thesis_sci_1993_donaldson_stephen_richard.pdf
Size:
2.53 MB
Format:
Adobe Portable Document Format
Description:
Download
Collections
Masters