Rudimentary Predicates and Relative Computation

Cited In (38)

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

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)