Rudimentary relations and primitive recursion: A toolbox

DOI10.1016/S0304-3975(97)00002-9zbMATH Open0896.03031OpenAlexW2010307931MaRDI QIDQ1127532FDOQ1127532

Authors: Henri-Alex Esbelin, Malika More 

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

Recommendations

• Primitive recursive equivalence relations and their primitive recursive complexity
• On rudimentarity, primitive recursivity and representability
• Primitive recursion and \(\mu\)-recursivity
• Primitive recursion, equality, and a universal set
• Rudimentary recursion, gentle functions and provident sets
• The realm of primitive recursion
• A proof-theoretic account of primitive recursion and primitive iteration
• Elementary descent recursion and proof theory
• On the Algebraic Structure of Primitive Recursive Functions
• scientific article; zbMATH DE number 1300970

zbMATH Keywords

countingcodingprimitive recursionrudimentary relations

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• Bounded minimalisation and bounded counting in argument-bounded idc's
• Title not available (Why is that?)
• The role of rudimentary relations in complexity theory
• On the polynomial computability of some rudimentary predicates.
• Complexity-theoretic hierarchies induced by fragments of Gödel's \(T\)
• Fifty years of the spectrum problem: survey and new results
• Arithmetical definability and computational complexity
• Extensions of MSO and the monadic counting hierarchy
• On rudimentarity, primitive recursivity and representability
• Reachability in fixed VASS: expressiveness and lower bounds
• Counting modulo finite semigroups
• Nonerasing, counting, and majority over the linear time hierarchy

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

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