The Simulated Tree-Growth Algorithm Based on T-Invariants for State Reduction of Petri Nets

Petri net is a powerful tool for analyzing and verifying complex systems due to its intuition and inherent concurrency. One major limitation of Petri net approaches is the state explosion problem. Although there are various methods to tackle this problem, the heuristic approaches are used little. In this paper, we propose a heuristic method for state space reduction of Petri nets. The heuristic is derived from state equation and minimal T-invariants, based on which a simulated tree-growth algorithm (STGA) is proposed to generate the state space. The key point of the STGA is the fitness evaluation. Concretely, we design an efficient algorithm to estimate the distance from each state to the target. By this heuristic, the state space can be generated heuristically rather than randomly, then only partial states are generated, which means the state explosion problem can be alleviated. Finally, the empirical study reveals the promising result of our proposal in this paper.