Affordable Access

Publisher Website

Control structures in programs and computational complexity

Annals of Pure and Applied Logic
Publication Date
DOI: 10.1016/j.apal.2004.10.011
  • Implicit Computational Complexity
  • Imperative Programming Languages
  • Grzegorczyk Hierarchy
  • Higher Type Recursion
  • Lambda Calculus
  • Polynomial Time
  • Computer Science


Abstract A key problem in implicit complexity is to analyse the impact on program run times of nesting control structures, such as recursion in all finite types in functional languages or for-do statements in imperative languages. Three types of programs are studied. One type of program can only use ground type recursion. Another is concerned with imperative programs: ordinary loop programs and stack programs. Programs of the third type can use higher type recursion on notation as in functional programming languages. The present approach to analysing run time yields various characterisations of fptime and all Grzegorczyk classes at and above the flinspace level. Central to this approach is the distinction between “top recursion” and “side recursion”. Top recursions are the only form of recursion which can cause an increase in complexity. Counting the depth of nested top recursions leads to several versions of “the μ -measure”. In this way, various recent solutions of key problems in implicit complexity are integrated into a uniform approach.

There are no comments yet on this publication. Be the first to share your thoughts.


Seen <100 times

More articles like this

On computational complexity of Prolog programs

on Theoretical Computer Science Jan 01, 1993

The computational complexity of some fuzzy dynamic...

on Computers & Mathematics with A... Jan 01, 1999

Alternation and the computational complexity of lo...

on The Journal of Logic Programmi... Jan 01, 1984

The Garland Measure and Computational Complexity o...

on Electronic Notes in Theoretica... Nov 28, 2003
More articles like this..