Unravelling Unstructured Programs

It is shown that structured schemas always require an increase in space-time requirements, and it is suggested that this increase can be used as a complexity measure for the original schema.

Abstract

A method is presented for converting unstructured program schemas to strictly equivalent structured form. The predicates of the original schema are left intact with structuring being achieved by the duplication of the original decision nodes without the introduction of compound predicate expressions, or, where possible, by function duplication alone. It is shown that structured schemas must have at least as many decision nodes as the original unstructured schema, and must have more when the original schema contains branches out of alternation constructs. The structuring method allows the complete avoidance of function duplication, but only at the expense of decision node duplication. It is shown that structured schemas always require an increase in space–time requirements, and it is suggested that this increase can be used as a complexity measure for the original schema.