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

DOI10.1017/S0960129510000198zbMath1216.03053OpenAlexW2161599677MaRDI QIDQ3060189

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

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

Cites Work

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