Annals of Pure and Applied Logic 75 (1-2):153-178 (1995)

We investigate a simply typed term system ℘R ω aimed at defining partial primitive recursive functionals over arbitrary Scott domains . A hierarchy of complexity classes R n ω for functionals definable in ℘R ω is given based on a hierarchy of term classes ℘R n ωpn denoting the n th class of so-called prenormal terms . They come into play by the key observation that every term t can be transformed by what we call higher type modularization as a kind of inversion of normalization into an αβη equal term t ′ having almost no structural complexity. However, it turns out that normalization of a prenormal term may increase its structural complexity with respect to the classes ℘R n ωpn , and conversely, ground type modularization being still possible may reduce it. Thus the structural complexity of a prenormal term t defined as the least n with t ϵ ℘R n ωpn depends strongly on the representation of t . We present a measure denoted μ = n rel v , ϱ for prenormal terms t to be read as t is of complexity n with valued free variables v and valued type π . It is shown that μ is stable on αβη equal terms and furthermore, μ ⩽ min {n |∃t′ ϵ ℘R n ω pn .t′ = αβη t} . Moreover, if t is in a certain μ- normal form 2, the estimate above is even true with equality, that is μ yields the structural complexity of the maximal modularization of t , clearly the best a purely structural measure can do. μ-normal forms 2 do not always exist. The counterexample we give, however, clearly shows that μ does not only take into account the structural complexity of a prenormal term but also the nature and computationl complexity of the algorithm it represents
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(94)00062-8
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 58,398
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Subrecursive Hierarchies on Scott Domains.Karl-Heinz Niggl - 1993 - Archive for Mathematical Logic 32 (4):239-257.

Add more references

Citations of this work BETA

Mω Considered as a Programming Language.Karl-Heinz Niggl - 1999 - Annals of Pure and Applied Logic 99 (1-3):73-92.
< I> M_< Sup> Ω Considered as a Programming Language.Karl-Heinz Niggl - 1999 - Annals of Pure and Applied Logic 99 (1):73-92.

Add more citations

Similar books and articles

Towards the Computational Complexity of ℘Rω-Terms.Karl-Heinz Niggl - 1995 - Annals of Pure and Applied Logic 75 (1):153-178.
Control Structures in Programs and Computational Complexity.Karl-Heinz Niggl - 2005 - Annals of Pure and Applied Logic 133 (1-3):247-273.
Computation Models for Parameterized Complexity.Marco Cesati & Miriam Dilanni - 1997 - Mathematical Logic Quarterly 43 (2):179-202.
Computational Complexity and Godel's Incompleteness Theorem.Gregory J. Chaitin - 1970 - [Rio De Janeiro, Centro Técnico Científico, Pontifícia Universidade Católica Do Rio De Janeiro.
Deterministic Chaos and Computational Complexity: The Case of Methodological Complexity Reductions. [REVIEW]Theodor Leiber - 1999 - Journal for General Philosophy of Science / Zeitschrift für Allgemeine Wissenschaftstheorie 30 (1):87-101.
Computational Complexity on Computable Metric Spaces.Klaus Weirauch - 2003 - Mathematical Logic Quarterly 49 (1):3-21.


Added to PP index

Total views
6 ( #1,076,293 of 2,420,545 )

Recent downloads (6 months)
1 ( #542,979 of 2,420,545 )

How can I increase my downloads?


My notes