SYNCHRONIC-DISTANCE, FAIRNESS, AND MAXIMUM CONCURRENCY PROBLEMS FOR PETRI NETS

The first topic of this thesis is synchronic distance which represents mutual interdependences between the execution of transitions in a Petri net. We introduce the notion of synchronic distance matrix and suggest a method for finding a marked graph from a given synchronic distance matrix. A formula to compute the synchronic distance in a live marked graph is presented.;Finally, as the third topic, this thesis discusses the properties and applications of a token distance matrix in a marked graph. One of the applications is a method for identifying a maximum set of instructions (nodes) that can be executed (fired) concurrently in a decision-free concurrent system. This method can be applied to estimating the minimum number of processors that is required to execute concurrently all enabled instructions at any time during a data flow computation.;The second topic is concerned with the maximum firing deviation between two transitions (or two subsets of transitions) which is defined as the maximum firing slack that can be obtained in all possible firing sequences or subsequences. Bounded fairness (B-fairness) is defined as a symmetric value based on the concept of firing deviation. The B-fair relation is an equivalence relation on the set of transitions in a bounded Petri net. We present necessary and sufficient conditions for B-fair relations and methods for finding a subset of transitions which are in a B-fair relation with a given transition (or a given subset of transitions). The relationships among various concepts of fairness, such as bounded fairness, unconditional fairness, strong fairness, weak fairness, etc. are investigated. In addition, the above concepts of fairness are generalized to those with respect to subsets and coverings of transitions.