Well-formed generalized task graphs
Mohammad Ghodsi, Krishna Kant · 2002
Generalized task graphs further extend the well-known extended task graphs by introducing a new node which provides the 1-out-of-n type of completion semantics along with abortion of certain computations. This extension allows modeling of problems involving parallel state-space search and exception handling. Arbitrary generalized task graphs may not be 'well-formed', i.e. they may not represent meaningful parallel computation. The paper gives necessary and sufficient conditions for the well-formedness of such task graphs, by viewing them as high level Petri nets. It also presents a method for checking these conditions based on the structural analysis.>