The realm of primitive recursion

DOI10.1007/BF01620765zbMath0659.03025OpenAlexW2034895188MaRDI QIDQ1112020

Harold Simmons

Publication date: 1988

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01620765

zbMATH Keywords

primitive recursive functions

Mathematics Subject Classification ID

Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (24)

Two function algebras defining functions in \(\mathsf{NC}^k\) Boolean circuits ⋮ A new “feasible” arithmetic ⋮ Unification of infinite sets of terms schematized by primal grammars ⋮ Intrinsic theories and computational complexity ⋮ Characterizing parallel time by type 2 recursions with polynomial output length ⋮ Analysing the implicit complexity of programs. ⋮ Build your own clarithmetic I: Setup and completeness ⋮ Recursion Schemata for NC k ⋮ A characterization of alternating log time by ramified recurrence ⋮ Pointwise Transfinite Induction and a Miniaturized Predicativity ⋮ Term rewriting theory for the primitive recursive functions ⋮ An arithmetic for polynomial-time computation ⋮ Tiering as a Recursion Technique ⋮ Tiered Arithmetics ⋮ Dependency Pairs and Polynomial Path Orders ⋮ A note on complexity measures for inductive classes in constructive type theory ⋮ Separating NC along the \(\delta\) axis ⋮ On the computational complexity of imperative programming languages ⋮ Higher type recursion, ramification and polynomial time ⋮ Implicit characterizations of FPTIME and NC revisited ⋮ Ramified recurrence and computational complexity. III: Higher type recurrence and elementary complexity ⋮ Implicit recursion-theoretic characterizations of counting classes ⋮ A new order-theoretic characterisation of the polytime computable functions ⋮ Functions over free algebras definable in the simply typed lambda calculus

Cites Work

• Eine Klassifikation der ε₀‐Rekursiven Funktionen
• Unnamed Item

This page was built for publication: The realm of primitive recursion