There are many different types of decomposition that can be considered. Based on her understanding
of the problem, the decomposer has to make a decision on how to decompose a given problem,
for example, by meeting certain constraints on the size of the sub-problems, or constraints on
the way that solved sub-problems ought to be recomposed. A simple and natural way of decomposition
is sequential decomposition in which a task is decomposed into two sub-tasks, where the first
sub-task is to be carried out before the second sub-task can be executed. A formal model
for sequential decomposition is the subject of this work. We assume that the given problem is specified
by means of an input/output relation. It is widely accepted that such relations are the most
general way to specify programs, whether for terminating programs [1]}, where input and output
should be related values, or for nonterminating programs [2]}, where input and output are
streams of values. The decomposition problem is to decompose a given input/output relation \(R\) ,
between an input domain \(\mathcal {I}\)  and an output domain \(\mathcal {O}\) , into two relations \(R_1\)  and \(R_2\) , such that
\(R\)  can be reconstructed from \(R_1\)  and \(R_2\)  using relational composition
(defined in Section ).
To avoid trivial solutions, where either \(R_1\)  or \(R_2\)  is the identity relation, we assume that the
intermediate domain, that is, the co-domain of \(R_1\) , which is also the domain of \(R_2\) , is specified.
Intuitively, specifying the intermediate domain amounts to constraining the manner in which the first
task can “communicate” with the second task. Such a restriction can be viewed as a form of
information hiding, which is one of the major criteria for decomposition in [3]}.
As we show, sequential decomposition is nontrivial only when the channel of communication between the
first and second task has a small ”bandwidth”, appropriately defined.
