Linear Time S-Component Extraction for General Petri Nets

Abstract

In this work, we present a linear time, S-component extraction algorithm capable of handling strongly connected, General Petri Nets. Most prior works have focused exclusively on Free-Choice or Extended Free-Choice Nets. We generalise S-component extraction to General Petri Nets, providing a fast transformation between event and state-based spaces. This work is directly applicable to Petri Net based logic synthesis, as a Petri Net event model describing a system's behaviour, may be mapped to a set of S-components, and eventually interacting on Multiple Synchronised FSMs (MSFMSs) [1], implemented in synchronous or asynchronous Boolean Logic. We have tested a set of 25 Petri Net benchmarks, including FSMs, Marked Graphs, Free-Choice, Extended Free-Choice, Asymmetric Choice and General Petri Nets. Our algorithm managed to successfully generate correct S-covering results for all of them. We present results against the original algorithm of [2]. The S-component extraction algorithm complexity is O(P+T+F). © 2019 IEEE.