Hsin-Hung Chou and De-Ron Liang
A computation task running in distributed systems can be represented as a directed graph, called as a task graph. In such graph, vertices represent modules and arcs represent precendence constraints. And the arguments are passing among the modules. In the past, people study such subjects on edge series-parallel(ESP) digraph. In an ESP digraph, the precedence relation among the arcs joining to a vertex defaults to be OR-relation. In this paper, we extend the precedence relation to being a factorable formulas. Such digraphs are called and-or series-parallel(AOSP) digraph. And we present a polynomial time algorithm to recognize the class of the AOSP digraphs.