{"id":{"repo_id":"cape-town","oai_identifier":"oai:open.uct.ac.za:11427/16009"},"canonical_url":"https://search.dev.ndltd.org/etd/cape-town/oai:open.uct.ac.za:11427/16009","repository":{"repo_id":"cape-town","name":"University of Cape Town","base_url":"https://open.uct.ac.za/oai/request"},"display":{"title":"The complexity of Petri net transformations","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Donaldson, Stephen Richard"],"institution":"Department of Computer Science","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":["Kritzinger, Pieter S"],"committee_chairs":[],"committee_members":[],"year":1993,"date_issued":"1993","date_published":"1993","updated_at":"2026-07-24T01:33:42Z","subjects":[],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/11427/16009","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.advisor","label":"Advisor","values":["Kritzinger, Pieter S"]},{"key":"dc:creator","label":"Author","values":["Donaldson, Stephen Richard"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2015-12-28T06:11:39Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2015-12-28T06:11:39Z"]},{"key":"dc:date.issued","label":"Date","values":["1993"]},{"key":"dc:publisher.department","label":"Dc Publisher Department","values":["Department of Computer Science"]},{"key":"dc:publisher.institution","label":"Dc Publisher Institution","values":["University of Cape Town"]},{"key":"dc:type","label":"Dc Type","values":["Master Thesis"]},{"key":"dc:type.qualificationlevel","label":"Dc Type Qualificationlevel","values":["Masters"]},{"key":"dc:type.qualificationname","label":"Dc Type Qualificationname","values":["MSc"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/11427/16009"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Bibliography: pages 124-127."]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["The complexity of Petri net transformations"]}]}],"canonical_facts":{"dc:contributor.advisor":["Kritzinger, Pieter S"],"dc:creator":["Donaldson, Stephen Richard"],"dc:date.accessioned":["2015-12-28T06:11:39Z"],"dc:date.available":["2015-12-28T06:11:39Z"],"dc:date.issued":["1993"],"dc:description":["Bibliography: pages 124-127."],"dc:description.abstract":["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."],"dc:identifier.uri":["http://hdl.handle.net/11427/16009"],"dc:language.iso":["eng"],"dc:publisher.department":["Department of Computer Science"],"dc:publisher.institution":["University of Cape Town"],"dc:title":["The complexity of Petri net transformations"],"dc:type":["Master Thesis"],"dc:type.qualificationlevel":["Masters"],"dc:type.qualificationname":["MSc"]},"updated_at":"2026-07-24T01:33:42Z"}