Rudimentary Predicates and Relative Computation
From MaRDI portal
Publication:4154070
DOI10.1137/0207018zbMath0375.68030OpenAlexW2078123020MaRDI QIDQ4154070
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
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
