Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-26T19:53:21.892Z Has data issue: false hasContentIssue false
  • English
  • Français

Asymptotic Enumeration of Predicate-Junction Flowgraphs

Published online by Cambridge University Press:  12 September 2008

C. Cooper
C. Cooper
Affiliation:
School of Mathematical Sciences, University of North London, London N7 8DB, UK
Get access Rights & Permissions [Opens in a new window]

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
Combinatorics, Probability and Computing , Volume 5 , Issue 3 , September 1996 , pp. 215 - 226
Copyright
Copyright © Cambridge University Press 1996

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Fenton, N. E. (1991) Software Metrics: A Rigorous Approach. Chapman & Hall.Google Scholar
[2]Fenton, N. E. and Hill, G. (1992) Systems Construction and Analysis, A Mathematical and Logical Framework. McGraw-Hill.Google Scholar
[3]Hecht, M. S. (1977) Flow Analysis of Computer Programs. North-Holland.Google Scholar
[4]Zuse, H. (1991) Software Metrics: Tools and Techniques, de Gruyter.Google Scholar
[5]Dijkstra, E. W. (1968) Go to statement considered harmful. Comm. ACM 11(03) 147–148.CrossRefGoogle Scholar
[6]Böhm, C. and Jacopini, G. (1966) Flow-diagrams, Turing machines, and languages with only two formation rules. Comm. ACM 9(04) 366–371.CrossRefGoogle Scholar
[7]Knuth, D. E. (1974) Structured programming with GOTO statement. Comput. Surv. 6(4) 261–301.CrossRefGoogle Scholar
[8]Bender, E. A. and Butler, J. T. (1985) Enumeration of structured flowcharts. J. ACM 32(3) 537–548.CrossRefGoogle Scholar
[9]Linger, R. C., Mills, H. D. and Witt, B. I. (1979) Structured Programming: Theory and Practice. Addison-Wesley.Google Scholar
[10]Prather, R. E. (1993) Hierarchical metrics and the prime generation problem. Software Eng. J. (09) 246–252.CrossRefGoogle Scholar
[11]Bollobás, B. (1985) Random Graphs. Academic Press.Google Scholar
[12]Barbour, A. D., Hoist, L. and Janson, S. (1992) Poisson Approximation. Oxford University Press.CrossRefGoogle Scholar
[13]Arratia, R., Goldstein, L. and Gordon, L. (1990) Poisson approximation and the Chen-Stein method. Statistical Sci. 5(4) 403–434.Google Scholar
[14]Bondy, J. A. and Murty, U. S. R. (1976) Graph Theory With Applications. North Holland.CrossRefGoogle Scholar
[15]Bollobás, B. (1982) The asymptotic number of unlabelled regular graphs. J. London Math. Soc. 26 (2) 201–206CrossRefGoogle Scholar