Rudimentary Predicates and Relative Computation

Cited in

(38)

Rudimentary relations and primitive recursion: A toolbox
How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic q
Extensional Uniformity for Boolean Circuits
Observations on complete sets between linear time and polynomial time
A descriptive complexity approach to the linear hierarchy.
An exploration of the partial respects in which an axiom system recognizing solely addition as a total function can verify its own consistency
Bounded query machines: on NP and PSPACE
Fifty years of the spectrum problem: survey and new results
Self-verifying axiom systems, the incompleteness theorem and related reflection principles
Time-space tradeoffs for satisfiability
European Summer Meeting of the Association for Symbolic Logic, (Logic Colloquium '87), Granada, Spain, 1987
Regular graphs and the spectra of two-variable logic with counting
Rudimentary reductions revisited
A generalization of the second incompleteness theorem and some exceptions to it
Characterizations of reduction classes modulo oracle conditions
Bounded arithmetic, proof complexity and two papers of Parikh
On the available partial respects in which an axiomatization for real valued arithmetic can recognize its consistency
On the correspondence between arithmetic theories and propositional proof systems – a survey
Bounded minimalisation and bounded counting in argument-bounded idc's
Nonerasing, counting, and majority over the linear time hierarchy
Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem
Complexity of Boolean algebras
On languages specified by relative acceptance
Alternating real-time computations
Representations of language families by homomorphic equality operations and generalized equality sets
Arithmetical definability and computational complexity
On quasilinear-time complexity theory
End-extensions of models of weak arithmetic from complexity-theoretic containments
Logical Closure Properties of Propositional Proof Systems
A Characterisation of the Relations Definable in Presburger Arithmetic
The role of rudimentary relations in complexity theory
Extensions of MSO and the monadic counting hierarchy
The minimum oracle circuit size problem
Deterministic summation modulo \(\mathcal B_{n}\), the semigroup of binary relations on \(0,1, \dots, n-1\)
First order logic, fixed point logic and linear order
A theory for Log-Space and NLIN versus co-NLIN
\(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)
Bounded query machines: on NP( ) and NPQUERY( )

This page was built for publication: Rudimentary Predicates and Relative Computation

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