Bounded minimalisation and bounded counting in argument-bounded idc's

DOI10.1017/S0960129510000198zbMATH Open1216.03053OpenAlexW2161599677MaRDI QIDQ3060189FDOQ3060189

Authors Mathias Barra

Publication date 1 December 2010

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0960129510000198

zbMATH Keywords

fragments of first-order logicinductively defined classesargument-bounded initial functionsbounded counting schematabounded minimalisation

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Recursive functions and relations, subrecursive hierarchies (03D20)

Recommendations

• scientific article; zbMATH DE number 3841837
• Arithmetizing uniform \(NC\)
• Bounded arithmetic for NC, ALogTIME, L and NL
• scientific article; zbMATH DE number 704020
• scientific article; zbMATH DE number 1670480

Cites work

• A Characterisation of the Relations Definable in Presburger Arithmetic
• Arithmetic, first-order logic, and counting quantifiers
• Complexity classes and fragments of C
• LOGSPACE and PTIME characterized by programming languages
• Neat function algebraic characterizations of LOGSPACE and LINSPACE
• On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation
• Rudimentary Predicates and Relative Computation
• Rudimentary relations and primitive recursion: A toolbox
• Small Grzegorczyk classes and limited minimum
• The Structure of Detour Degrees
• The expressive power of higher-order types or, life without CONS
• Theory of Formal Systems. (AM-47)

This page was built for publication: Bounded minimalisation and bounded counting in argument-bounded idc's

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