Decidability Analysis of Some Classes of Extended Function Petri Net

摘要

In this report, we study liveness and reach ability problem of extended function Petri net with some structural restriction. Petri net is a mathematical model for concurrent systems such as parallel computers, manufacturing system, communication protocol and so on. Liveness and reach ability are important problems of Petri net. The former is to verify whether the system has no local deadlocks. The latter is to verify whether the system can reach the target status from the initial one. Extended function Petri net, where each arc weight is a function of the marking, has wide range of application including system biology, communication protocol and so on. However, it is hard to obtain theoretical results for general extended Petri net. First, we show liveness criterion of extended Petri net with asymmetric choice structure and extended free choice structure with some restricted arc functions. Then reach ability and liveness of extended Petri net with asymmetric choice structure is shown to be undecidable.