On Computation Complexity of the Concurrently Enabled Transition Set Problem
Li Pan1 
, Weidong Zhao1, Zhicheng Wang1, Gang Wei1 and Shumei Wang1
| (1) |
Tongji University, Shanghai 200092, CAD Research Center, China |
Abstract
In this paper, we propose a new decision problem, called the concurrently enabled transition set problem, which is proved
to be NP-complete by reduction from the independent set problem. Then, we present a polynomial-time algorithm for the maximal
concurrently enabled transition set problem, and prove that some special subproblems are in P by the proposed algorithm.
References secured to subscribers.