✦ LIBER ✦

Complexity classes of provable recursive functions

✍ Scribed by Dan Gordon

Publisher: Elsevier Science
Year: 1979
Tongue: English
Weight: 582 KB
Volume: 18
Category: Article
ISSN: 0022-0000
DOI: 10.1016/0022-0000(79)90037-0

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Classes of One-Argument Recursive Functi

Classes of One-Argument Recursive Functions

✍ Nadejda V. Georgieva 📂 Article 📅 1976 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 1 views

Plain Bases for Classes of Primitive Rec

Plain Bases for Classes of Primitive Recursive Functions

✍ Stefano Mazzanti 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 180 KB 👁 1 views

Classes of Recursive Functions and Their

Classes of Recursive Functions and Their Index Sets

✍ F. D. Lewis 📂 Article 📅 1971 🏛 John Wiley and Sons 🌐 English ⚖ 237 KB 👁 1 views

A learning-theoretic characterization of

A learning-theoretic characterization of classes of recursive functions

✍ Martin Kummer 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 673 KB

Inherent Complexity of Recursive Queries

✍ Stavros Cosmadakis 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 223 KB

We give lower bounds on the complexity of certain Datalog queries. Our notion of complexity applies to compile-time optimization techniques for Datalog; thus, our results indicate limitations of these techniques. The main new tool is linear first-order formulas, whose depth (respectively, number of

Provably total functions of Basic Arithm

Provably total functions of Basic Arithmetic

✍ Saeed Salehi 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 134 KB

## Abstract It is shown that all the provably total functions of Basic Arithmetic BA, a theory introduced by Ruitenburg based on Predicate Basic Calculus, are primitive recursive. Along the proof a new kind of primitive recursive realizability to which BA is sound, is introduced. This realizability