About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Paper
A semantically meaningful characterization of reducible flowchart schemes
Abstract
A "scalar" flowchart scheme, i.e. one with a single begin "instruction" is reducible iff its underlying flowgraph is reducible in the sense of Cocke and Allen or Hecht and Ullman. We characterize the class of reducible scalar flowchart schemes as the smallest class containing certain members and closed under certain operations (on and to flowchart schemes). These operations are "semantically meaningful' in the sense tha operations of the same form are meaningful for "the" functions (or partial functions) computed by interpreted flowchart schemes; moreover, the schemes and the functions "are related by a homomorphism." By appropriately generalizing "flowgraph" to (possibly) several begins (i.e. entries) we obtain a class of reducible "vector" flowchart schemes which can be characterized in a manner analogous to the scalar case but involving simpler more basic operations (which are also semantically meaningful). A significant side effect of this semantic viewpoint is the treatment of multi-exit flowchart schemes on an equal footing with single exit ones. © 1979.