Decomposition of Sequential Behavior Using Interface Specification and Complementation

Decomposition of system behavior along functional boundaries into interacting sequential components is a key step intop-down system design. In this paper, we present sequential decomposition, a method for factoring sequential componentsfrom a system specification based on interface specifications of the components. The resulting components can beindependently synthesized, or realized using off-the-shelf components. We introduce interface specification language (ISL),based on finite-state machine semantics, to specify the input/output behavior of synchronous sub-systems. A component isfactored from a system by embedding an implementation of the complement of its interface into the system description. Thecomposition of a machine with its complement is shown to be isomorphic to the machine, and the composition of a machinewith an implementation of its component is shown to be a safe interaction. We apply sequential decomposition to anon-trivial example, a special-purpose computer with Scheme programming language primitives as its instructions