Degree Type

Thesis

Date of Award

2010

Degree Name

Master of Science

Department

Computer Science

First Advisor

Andrew Miner

Abstract

Petri nets are a graph based formalism used for modelling concurrent systems. Binary Decision Diagrams or Multi-Valued Decision Diagrams can be used in the analysis of systems modelled by Petri nets. An encoding scheme is required to be able to map the Petri net state to decision diagram values. Various encodings like One-hot scheme, logarithmic scheme and Mdd scheme exist for this purpose. This thesis compares the performance of the existing encodings based on time and space taken to represent and analyze the system modelled as Petri net. It also introduces and compares a new encoding scheme called k-hot encoding and shows a gradual improvement in performance of the scheme with increasing values of k. The process of analyzing properties like deadlock and starvation is explained and a comparison is made between the encoding schemes based on the time taken by each to analyze these properties.

Copyright Owner

Nishtha Arora

Language

en

Date Available

2012-04-30

File Format

application/pdf

File Size

83 pages

Share

COinS