Program structures: Some new characterisations

AbstractIrreducible program fowgraphs are important in the study of program structuredness. In this paper a partial order is defined on the set of irreducible flowgraphs. This allows us to characterise those programs which can be re-structured by node splitting, where structuredness is defined in terms of any “subgraph-closed” set of irreducible flowgraphs. This includes all sets of structural components available in modern programming languages such as Ada, Modula-2, and C. In particular, we apply our results to the study of multiple-exit and multilevel exit control structures, giving a new characterisation of the BJn-charts of Kosaraju and a sharpening of two results of Peterson, Kasami, and Tokura