Akademik Veri Yönetim Sistemi
EXPERT SYSTEMS WITH APPLICATIONS, cilt.42, sa.1, ss.519-526, 2015 (SCI-Expanded)
This paper introduces leveled Petri nets (PNs), and proposes a novel PN analysis tool, the superposition chain (SC), to avoid state explosion. It also introduces underlying tools-superposition and the leveled token game-to tackle the P vs NP problem, a well known problem in CS/AI community. The leveled token game, defined over a leveled PN, generates the SC of the PN. The leveling is based on the transitions such that a transition and all its input places are in the same level, and that there is no causality among transitions in a level, while transitions across levels indicate causality. The enabling rule is extended by superposition and firing history. Superposition of markings is defined by a set (v) under barM of places p marked in superposition, and denotes that each p in (v) under barM is marked individually, yet it is uncertain if all p in (v) under barM are marked together. In other words, superposition loses which p in (v) under barM is marked by conflicting transitions, which are revealed by the transition firing history. The firing history of p is an element of (v) under barM is also defined by a set, h(p), and denotes transition firings participated in p is an element of (v) under barM, yet does not enumerate their firing sequences to avoid the state explosion. Then, the compound firing history defined over (v) under barM, h((v) under barM), is used to reveal all conflicting transitions participated in (v) under barM. Hence, (v) under barM is not coverable as a whole, if there are conflicting firings in h((v) under barM), which is used for the transition enabling. Consequently, the SC, generated by the leveled token game, specifies the PN behavior, as a reachability tree, generated by the (conventional) token game, also specifies a PN behavior. (C) 2014 Elsevier Ltd. All rights reserved.