In: Farn Wang (Ed.): Lecture Notes in Computer Science, Vol. 3299: Automated Technology for Verification and Analysis: Second International Conference, ATVA 2004, Taipei, Taiwan, ROC, October 31-November 3, 2004, pages 79-92. Springer-Verlag, 2004.
Abstract: Bounded model checking has received recent attention as an efficient verification method. The basic idea behind this new method is to reduce the model checking problem to the propositional satisfiability decision problem or SAT. However, this method has rarely been applied to Petri nets, because the ordinary encoding would yield a large formula due to the concurrent and asynchronous nature of Petri nets. In this paper, we propose a new SAT-based verification method for safe Petri nets. This method can reduce verification time by representing the behavior by very succinct formulas. Through an experiment using a suite of Petri nets, we show the effectiveness of the proposed method.
Keywords: Bounded model checking; SAT; Petri nets.