An Equational Axiomatization of the Algebra of Reducible Flowchart Schemes

The flowchart schemes called “reducible” are of interest because (1) they schematize programs without “go to” statements; (2) for every flowchart scheme there is a reducible one which is step-by-step equivalent to it; (3) they manipulate readily. The reducible flowchart schemes admit both graph-theoretic and algebraic descriptions. A flowchart scheme F with n begins and p exits is reducible iff both (a) for every vertex v there is a begin-path (i.e. a path from a begin vertex) which ends in v (b) for every closed path C there is a vertex vC of C such that every begin path to a vertex of C meets vC. Algebraically: F is reducible iff it can be built up from atomic flowchart schemes (which may be thought of as corresponding to single instructions) and surjective trivial flowchart schemes (which may be thought of as redirecting flow of control) by means of composition (∘), separated pairing (+), and scalar iteration (†). Dropping † yields the accessible, acyclic flowchart schemes.