The computation task of a distributed processing system usually can be partitioned into

a set of modules and then modeled as a directed graph, called the task digraph. In the task

digraph, vertices represent modules and arcs represent message passing links between two

modules. Particularly, according to the logical structures and precedence relationships among

modules, a large class of task digraphs can be expressed by the combination of three common

types of subgraphs: sequential, And-Fork to And-Join (AFAJ) and Or-Fork to Or-Join

(OFOJ). This class of task digraphs has been modeled as And-Or Series-Parallel (AOSP)

digraphs. There is a certain probability, called the task reliability, associated with the event

that a task completes successfully.   This measure accurately models the reliability of a task

running in the system. The task reliability problem is known to be NP-hard for general

digraphs. But for AOSP digraphs, task reliability can be found in linear time. Moreover,

we can also precisely estimate task response time, which is the time from the invocation

of a task to the completion of its execution, in linear time for AOSP digraphs. Task response

time is an important design criterion for real-time computer systems. Hence, to examine if

a task digraph is an AOSP digraph becomes a useful work for evaluating computation tasks.

In this paper, we propose a polynomial time algorithm to recognize AOSP digraphs. The

logical structures among modules of an AOSP digraph will be formulated as Boolean formulas,

and such formulas own the defined fully factorable property. The main part of our work is the

factoring algorithm, which can fully factor a positive CNF.

Keywords: Task digraphs, Boolean formulas, graph recognition, distributed processing systems,
reliability, response time.