Existence of Forbidden Digraphs for Crisp Boolean Petri Nets

Abstract

Boolean Petri net (BPN) and Crisp Boolean Petri net (CBPN) is a well-studied graph model since 2010 which has several applications in mathematical modeling of complex or tricky networks. Modeling any network with Petri net which can generate binary numbers as marking vectors in its reachability tree is still has much uses. In CBPN with a minimum number of transition and minimum number of steps of reachability tree, minimal execution time to run the machine has not been noted till date, thus it’s necessary to sort out this problem. Possibly it may occur due to some forbidden structure which hinders any 1-safe Petri net to be a CBPN. In this paper, we present some forbidden digraphs whose presence interrupts the generation of binary n-vectors exactly once. Any 1-safe Petri net is not a CBPN if it contains any of the subnet induced to the four forbidden structures discussed in this paper.

Keywords

• petri net
• binary vectors
• boolean petri net
• crisp boolean petri net
• forbidden graphs