Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10118892 | Annals of Pure and Applied Logic | 2005 | 27 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Logic
Authors
Karl-Heinz Niggl,