The number of states is a very important matter for model checking approach in Petri net's analysis. We first gave a formal definition of state number calculation problem: For a Petri net with an initial state (marking), how many states does it have? Next we showed the problem cannot be solved in polynomial time for a popular subclass of Petri nets, known as free choice workflow nets, if P≠NP. Then we proposed a polynomial time algorithm to solve the problem by utilizing a representational bias called as process tree. We also showed effectiveness of the algorithm through an application example.

Response property is a kind of liveness property. Response property problem is defined as follows: Given two activities α and β, whenever α is executed, is β always executed after that? In this paper, we tackled the problem in terms of Workflow Petri nets (WF-nets for short). Our results are (i) the response property problem for acyclic WF-nets is decidable, (ii) the problem is intractable for acyclic asymmetric choice (AC) WF-nets, and (iii) the problem for acyclic bridge-less well-structured WF-nets is solvable in polynomial time. We illustrated the usefulness of the procedure with an application example.

Many actual systems, e.g. computer programs, can be modeled as a subclass of Petri nets, called bridge-less workflow nets. For bridge-less workflow nets, we revealed the following properties: (i) any acyclic bridge-less workflow net is free choice; (ii) an acyclic bridge-less workflow net is sound iff it is well-structured; and (iii) any sound bridge-less workflow net is well-structured. We also proposed a necessary and sufficient condition to decide whether a given workflow net is bridge-less, and then constructed a polynomial-time procedure for it.