Rudimentary Predicates and Relative Computation

DOI10.1137/0207018zbMath0375.68030OpenAlexW2078123020MaRDI QIDQ4154070

Celia Wrathall

Publication date: 1978

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0207018

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Turing machines and related notions (03D10)

Related Items (37)

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

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