Analysis and synthesis of generalized task graphs

The author introduces the notion of generalized task graphs (GTG), that are useful in specifying the behavior of a richer class of concurrent programs than the classical task graphs. In general, such task graphs are not well-formed; therefore, the author examines necessary and sufficient conditions for well formedness. He introduces an algebra for describing well formed GTGs and shows how it can be exploited in synthesis, i.e. composing several GTGs into a single compact GTG, and analysis, i.e. obtaining completion time distributions