On the Regularity of Petri Net Languages
Resource
Information and Computation 124 (2): 168-181
Journal
Information and Computation
Journal Volume
124
Journal Issue
2
Pages
168-181
Date Issued
1996
Date
1996
Author(s)
Abstract
Petri nets are known to be useful for modeling concurrent systems. Once modeled by a Petri net, the behavior of a concurrent system can be characterized by the set of all executable transition sequences, which in turn can be viewed as a language over an alphabet of symbols corresponding to the transitions of the underlying Petri net. In this paper, we study the language issue of Petri nets from a computational complexity viewpoint. We analyze the complexity of the regularity problem (i.e., the problem of determining whether a given Petri net defines an irregular language or not) for a variety of classes of Petri nets, including conflict-free, trap-circuit, normal, sinkless, extended trap-circuit, BPP, and general Petri nets. (Extended trap-circuit Petri nets are trap-circuit Petri nets augmented with a specific type of circuits. ) As it turns out, the complexities for these Petri net classes range from NL (nondeterministic logspace), PTIME (polynomial time), and NP (nondeterministic polynomial time), to EXPSPACE (exponential space). In the process of deriving the complexity results, we develop a decomposition approach which, we feel, is interesting in its own right, and might have other applications to the analysis of Petri nets as well. As a by-product, an NP upper bound of the reachability problem for the class of extended trap-circuit Petri nets (which properly contains that of trap-circuit (and hence, conflict-free) and BPP-nets, and is incomparable with that of normal and sinkless Petri nets) is derived. © 1996 Academic Press, Inc.
Type
journal article
File(s)![Thumbnail Image]()
Loading...
Name
09.pdf
Size
803.8 KB
Format
Adobe PDF
Checksum
(MD5):93b8ea3804f64e72e83579cde030b08b