Title :
Well-formed generalized task graphs
Author :
Ghodsi, M. ; Kant, K.
Author_Institution :
Dept. of Comput. Sci., Sharif Univ. of Technol., Tehran, Iran
Abstract :
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
Keywords :
Petri nets; graph theory; parallel algorithms; parallel processing; completion semantics; generalized task graphs; high level Petri nets; necessary and sufficient conditions; parallel exception handling; parallel state-space search; Abortion; Artificial intelligence; Computer science; Concurrent computing; Fault trees; Game theory; Petri nets; Sufficient conditions;
Conference_Titel :
Parallel and Distributed Processing, 1991. Proceedings of the Third IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2310-1
DOI :
10.1109/SPDP.1991.218221