Towards the computational complexity of PR^ -terms

DOI10.1016/0168-0072(94)00062-8MaRDI QIDQ1899150zbMATH OpenOpenAlexFDO

Authors Karl-Heinz Niggl

Publication date 14 February 1996

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(94)00062-8

zbMATH Keywords

partial primitive recursive functionalsprenormal termsstructural complexity

Mathematics Subject Classification ID

Theory of programming languages (68N15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Semantics in the theory of computing (68Q55)

Recommendations

• scientific article; zbMATH DE number 873331
• The \(\mu\)-measure as a tool for classifying computational complexity
• Computational Complexity Via Finite Types
• \({\mathcal M}^\omega\) considered as a programming language

Cites work

• A type-theoretical alternative to ISWIM, CUCH, OWHY
• scientific article; zbMATH DE number 3780545 (Why is no real title available?)
• scientific article; zbMATH DE number 65741 (Why is no real title available?)
• scientific article; zbMATH DE number 512774 (Why is no real title available?)
• scientific article; zbMATH DE number 3451842 (Why is no real title available?)
• scientific article; zbMATH DE number 785043 (Why is no real title available?)
• scientific article; zbMATH DE number 873331 (Why is no real title available?)
• LCF considered as a programming language
• Recursion on the partial continuous functionals
• Subrecursive hierarchies on Scott domains

Cited in

(4)

• \({\mathcal M}^\omega\) considered as a programming language
• The \(\mu\)-measure as a tool for classifying computational complexity
• Separating NC along the \(\delta\) axis
• \(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)

This page was built for publication: Towards the computational complexity of \(\mathcal{PR}^ \omega\)-terms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1899150)