Properties for software complexity measures are discussed. It is shown that a collection of nine properties suggested by E.J. Weyuker is inadequate for determining the quality of a software complexity measure. (see ibid., vol.14, p.1357-65, 1988). A complexity measure which satisfies all nine of the properties, but which has absolutely no practical utility in measuring the complexity of a program is presented. It is concluded that satisfying all of the nine properties is a necessary, but not sufficient, condition for a good complexity measure.>

Inductive inference, the automatic synthesis of programs, bears certain ostensible relationships with program testing. For inductive inference, one must take a finite sample of the desired input/output behavior of some program and produce (synthesize) an equivalent program. In the testing paradigm, one seeks a finite sample for a function such that any program (in a given set) which computes something other than the object function differs from the object function on the finite sample. In both cases, the finite sample embodies sufficient knowledge to isolate the desired program from all other possibilities. These relationships are investigated and general recursion theoretic properties of testable sets of functions are exposed.

Transformations of reducible flowcharts to REPEAT-EXIT or ${\text{RE}}_n $-charts and transformations of ${\text{RE}}_n $-charts to more structured forms are investigated. In particular, transformations within the hierarchy of flowcharts (D-charts, ${\text{RE}}_1 $-charts, ${\text{RE}}_2 $-charts,$ \cdots $, ${\text{RE}}_n $-charts, $ \cdots $) studied by Kosaraju [J. Comput. System Sci., 9 (1974), pp. 232–255] are presented. It is shown that the transformation of ${\text{RE}}_n $-charts to D-charts requires at most $\lceil \log _2 (n + 1) \rceil $ auxiliary Boolean variables (flags), and that for each $n \geqq 1$ this bound is tight for at least one ${\text{RE}}_n $-chart. The existence of a hierarchy of flowcharts with respect to the number of flags needed for conversion into equivalent D-charts is also shown.

A sunple programming language ffm IS defined for which a complete axiomatics is obtamable.Completeness is shown by presemmg a relauvely complete Hoare ax~omaUcs, demonstrating, by direct constmcuon, that the first-order theory of addmon ~+ as express,ve, and noting that ~+ Is complete.It is then shown that • ~m aS maxunal wath this property Further, a notton of complexity of a Hoare system is introduced based upon the lengths of proofs (dasregardmg proofs m the underlying logsc), and the system -~m, .~+ is shown to have polynomial complexity The nouon ts shown to be nontnvlal by presenting a language for which any Hoare axiom system has exponenual complextty rK~v WORDS AND PHRASES venficatmn, logic, complexity, theory of computation, programming languages, subrecurslve functions CR CATEGORIES' 5 21, 5 24, 5 25

Article A complete and consistent hoare axiomatics for a simple programming language Share on Authors: J. Cherniavsky SUNY at Stony Brook, N.Y. SUNY at Stony Brook, N.Y.View Profile , S. Kamin SUNY at Stony Brook, N.Y. SUNY at Stony Brook, N.Y.View Profile Authors Info & Claims POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languagesJanuary 1977 Pages 1–9https://doi.org/10.1145/512950.512951Online:01 January 1977Publication History 3citation179DownloadsMetricsTotal Citations3Total Downloads179Last 12 Months21Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A class of programs, $L_ + $, is introduced which lies between $L_1 $ and $L_2 $ in the loop program hierarchy. As a tool for analysis of this class, we use formulas in Presberger’s arithmetic and we show that $L_ + $ realizes these formulas both relationally and functionally. Moreover, the realization is exact in the sense that every program in $L_ + $ realizes some Presberger formula. Using known decidability and complexity results for Presberger's arithmetic, we are able to obtain a decision procedure for equivalence of $L_ + $ programs and to obtain upper bounds for the complexity of this procedure.