Rudimentary Predicates and Relative Computation

Cited in

(39)

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
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
First order logic, fixed point logic and linear order
A descriptive complexity approach to the linear hierarchy.
On languages specified by relative acceptance
The minimum oracle circuit size problem
A Characterisation of the Relations Definable in Presburger Arithmetic
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
Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem
A theory for Log-Space and NLIN versus co-NLIN
Self-verifying axiom systems, the incompleteness theorem and related reflection principles
Recursion-theoretic alternation
Extensions of MSO and the monadic counting hierarchy
Arithmetical definability and computational complexity
Rudimentary reductions revisited
Bounded query machines: on NP and PSPACE
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
Observations on complete sets between linear time and polynomial time
Rudimentary relations and primitive recursion: A toolbox
\(\Delta_ 0\)-complexity of the relation \(y= \prod_{i\leq n} F(i)\)
On the correspondence between arithmetic theories and propositional proof systems – a survey
Regular graphs and the spectra of two-variable logic with counting
Bounded query machines: on NP( ) and NPQUERY( )
On quasilinear-time complexity theory
Nonerasing, counting, and majority over the linear time hierarchy
Logical Closure Properties of Propositional Proof Systems
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)