Derivation of a Path-Connectivity Matrix for Tagged Flowcharts
Lawrence Yelowitz · Journal of the ACM · 1975
ABSTRXCT A procedure is given to derive a Boolean matrix M corresponding to a flowchart in which certain edges are dmtmgmshed as "tagged."For any pair of tagged edges z and 3, M(i, j) = 1 if and only if there is at least one flowchart path from * to 3 m which all of the mtermedmte edges are untagged Such a flowchart path is known as a "tagged path " Modifications to the procedure are then given that answer the related questions of determining the exact number of tagged paths as well as an explicit listing of these paths between two given edges.A computer representation is described which leads to efficmnt implementation of the procedure The flowcharts considered are budt only from IFTHENELSE, DOWHILE, and COMPOSITION control structures One of three possible edges from each DOWHILE is selected for tagging, in addmon, the unique input and output edge ~s tagged This procedure is useful in program certification systems, particularly mechanical systems, in which it is required to perform logical verifications over the set of all tagged paths