Article contents
Asymptotic Enumeration of Predicate-Junction Flowgraphs
Published online by Cambridge University Press: 12 September 2008
Abstract
We consider unlabelled flowgraphs for a model of binary logic without the constraints of structured programming. The number of such flowgraphs is asymptotic to (3.4n)n/2, where n is the number of nodes in the flowgraph. This is to be compared with bounds of between (8.8)n/2 and of (9.8)n/2 for unlabelled structured flowgraphs of the Böhm and Jacopini type. Of the space of flowgraphs we study, 41% are prime, that is contain no proper sub-flowgraphs. The main obstructions to primality being the Dijkstra-structures, which are based on If_Then_Else and Do_While constructs.
- Type
- Research Article
- Information
- Copyright
- Copyright © Cambridge University Press 1996
References
- 1
- Cited by