CaltechTHESIS
  A Caltech Library Service

Hierarchical Nets: A Structured Petri Net Approach to Concurrency

Citation

Choo, Young-il (1982) Hierarchical Nets: A Structured Petri Net Approach to Concurrency. Master's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechTHESIS:04022012-150759898

Abstract

Liveness and safeness are two key properties Petri nets should have when they are used to model asynchronous systems. The analysis of liveness and safeness for general Petri nets, though shown to be decidable by Mayr [1981], is still computationally expensive (Lipton [1976]). In this paper an hierarchical approach is taken: a class of Petri nets is recursively defined starting with simple, live and safe structures, becoming progressively more complex using net transformations designed to preserve liveness and safeness.

Using simple net transformations, nice nets, which are live and safe, are defined. Their behavior is too restrictive for modeling non-trivial systems, so the mutual exclusion and the repetition constructs are added to get µ-ρ-nets. Since the use of mutual exclusions can cause deadlock, and the use of repetitions can cause loss of safeness, restrictions for their use are given. Using µ-ρ-nets as the building blocks, hierarchical nets are defined. When the mutual exclusion and repetition constructs are allowed between hierarchical nets, distributed hierarchical nets are obtained. Examples of distributed hierarchical nets used to solve synchronization problems are given.

General net transformations not preserving liveness or safeness, and a notion of duality are presented, and their effect on Petri net behavior is considered.

Item Type:Thesis (Master's thesis)
Subject Keywords:Computer science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Restricted to Caltech community only
Research Advisor(s):
  • Kajiya, James Thomas
Thesis Committee:
  • Unknown, Unknown
Defense Date:2 November 1982
Record Number:CaltechTHESIS:04022012-150759898
Persistent URL:http://resolver.caltech.edu/CaltechTHESIS:04022012-150759898
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:6888
Collection:CaltechTHESIS
Deposited By: Benjamin Perez
Deposited On:02 Apr 2012 22:30
Last Modified:03 Dec 2014 00:04

Thesis Files

[img] PDF - Final Version
Restricted to Caltech community only
See Usage Policy.

3076Kb

Repository Staff Only: item control page