On Transforming Control Structures
John Keohane, John C. Cherniavsky, Peter B. Henderson · SIAM Journal on Computing · 1982
Transformations of reducible flowcharts to REPEAT-EXIT or ${\text{RE}}_n $-charts and transformations of ${\text{RE}}_n $-charts to more structured forms are investigated. In particular, transformations within the hierarchy of flowcharts (D-charts, ${\text{RE}}_1 $-charts, ${\text{RE}}_2 $-charts,$ \cdots $, ${\text{RE}}_n $-charts, $ \cdots $) studied by Kosaraju [J. Comput. System Sci., 9 (1974), pp. 232–255] are presented. It is shown that the transformation of ${\text{RE}}_n $-charts to D-charts requires at most $\lceil \log _2 (n + 1) \rceil $ auxiliary Boolean variables (flags), and that for each $n \geqq 1$ this bound is tight for at least one ${\text{RE}}_n $-chart. The existence of a hierarchy of flowcharts with respect to the number of flags needed for conversion into equivalent D-charts is also shown.