Rudimentary Predicates and Relative Computation

Cited in

(39)

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

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)