A study of structured Free Choice Petri nets
Jotwani, Naresh Dhanraj
Jump, J. Robert
Master of Science
A sub-class of the class of Free Choice Petri nets the class of Acyclic Free Choice Petri nets (AFCP nets) is first defined. After some of the properties of AFCP nets have been examined, a definition is made of Structured AFCP nets, i.e. AFCP nets which can be obtained by repeated top-down expansion, referred to as DU-Expansion, of an Acyclic Marked Graph (AMG). It is shown that an AFCP net is Structured if and only if it yields an AMG on repeated application to it of the process of DU-Reduction -- the converse of the process of DU-Expansion. An asynchronous control scheme, the Acyclic Control Structure (ACS), is then defined around AFCP nets. Definitions are made of the external behavior of the ACS and of the simulation of one ACS by another. A Structure Algorithm is presented which, given an ACS A, finds ACS Ag which simulates A and which is known to contain at least one subnet that can be collapsed by DU-Reduction. Theorems are presented proving the correctness of the algorithm. Finally, it is shown that any ACS can be simulated by a Structured ACS -- one built around a Structured AFCP net.