A Markov Model of Cyclic Structured Programs

Abstract

The paper defines a class of flow graphs which possess neither absorbing nor transient states. It gives a necessary and sufficient condition that any transition matrix associated with such a program be primitive. With a fixed flowgraph is associated an equivalence class of programs and an equivalence class of transition matrices. The paper investigates the hypothesis that the equivalence class of processes generated by the programs is modeled by the behavior of the equivalence class of eigenvectors generated by the transition matrices. The geometric implications are considered as well as the statistical behavior of the model as applied to the first fourteen algorithms of the Communications of the ACM.