On the Regularity of Petri Net Languages

ISSN： 0890-5401

Source： Information and Computation, Vol.124, Iss.2, 1996-02, pp. : 168-181

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.