A formal program complexity model and its application

This article takes an axiomatic approach to defining program complexity using complexity rankings and measures. A complexity ranking is an abstract, qualitative comparison between programs that is approximated by a complexity measure on each program. A set of axioms are stated and a classification scheme is presented with properties of each class. This is extended a series of properties developed by Weyuker. The formal model has many applications, including evaluating and classifying existing complexity measures and serving as criteria for complexity measure selection.