Rudimentary relations and primitive recursion: A toolbox

DOI10.1016/S0304-3975(97)00002-9zbMath0896.03031OpenAlexW2010307931MaRDI QIDQ1127532

Malika More, Henri-Alex Esbelin

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00002-9

zbMATH Keywords

countingcodingrudimentary relationsprimitive recursion

Mathematics Subject Classification ID

First-order arithmetic and fragments (03F30) Recursive functions and relations, subrecursive hierarchies (03D20)

Related Items (7)

Arithmetical definability and computational complexity ⋮ Extensions of MSO and the monadic counting hierarchy ⋮ Fifty years of the spectrum problem: survey and new results ⋮ Counting modulo finite semigroups ⋮ Bounded minimalisation and bounded counting in argument-bounded idc's ⋮ Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\) ⋮ Nonerasing, counting, and majority over the linear time hierarchy

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Super-exponentials nonprimitive recursive, but rudimentary
• Overspill and fragments of arithmetic
• The polynomial-time hierarchy
• Counting $Δ_0$ sets
• Theory of Formal Systems. (AM-47)
• Classes of Predictably Computable Functions
• Small Grzegorczyk Classes
• Small Grzegorczyk classes and limited minimum
• Expectations for Inbreeding Depression on Self-Fertilization of Tetraploids
• Rudimentary Predicates and Relative Computation
• Rudimentary Languages and Second‐Order Logic
• Context-free languages and rudimentary attributes

This page was built for publication: Rudimentary relations and primitive recursion: A toolbox