Dependency Analysis—A Petri Net Based Technique for Synthesizing Large Concurrent Systems

Yigang Chen, W. T. Tsai, Daniel Chao

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


Petri nets (PN’s) are frequently used in modeling, designing, and analyzing concurrent systems. A problem with PN’s, in the general case, is that they require high computational complexity to analyze their properties such as reachability, liveness, and boundedness. To avoid this problem, synthesis techniques have been suggested for constructing large PN’s. Using these techniques, the behavior of the constructed PN can be determined by local analysis which makes use of known properties of the given nets. Thus, the high computational complexity of global analysis is bypassed. This paper presents a new synthesis technique by exploring dependency relations in PN’s. It synthesizes large PN’s by combining smaller PN’s of arbitrary topology structures, and the combination can be verified efficiently by dependency analysis. A large system based on PN can be built up by repeated applications of the technique.

Original languageEnglish (US)
Pages (from-to)414-426
Number of pages13
JournalIEEE Transactions on Parallel and Distributed Systems
Issue number4
StatePublished - Apr 1993
Externally publishedYes


  • Boundedness
  • Petri net
  • dependency analysis
  • liveness
  • synthesis

ASJC Scopus subject areas

  • Signal Processing
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Dependency Analysis—A Petri Net Based Technique for Synthesizing Large Concurrent Systems'. Together they form a unique fingerprint.

Cite this