scientific article; zbMATH DE number 3995646

MaRDI QIDQ4723712zbMATH OpenFDO

Authors Alan R. Woods

Publication date 1986

zbMATH Keywords

\(\Delta _ 0\)-hierarchyalternating Turing machinealternations of bounded quantifiersbounded arithmeticconstant alternationfirst-order arithmetic with bounded quantifiers

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)

Recommendations

• On fixpoint arithmetic and infinite time Turing machines
• scientific article; zbMATH DE number 819737
• scientific article; zbMATH DE number 1344922
• scientific article; zbMATH DE number 4118351
• scientific article; zbMATH DE number 1070621
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories
• The computational power of bounded arithmetic from the predicative viewpoint
• scientific article; zbMATH DE number 1670480
• Publication:4893147
• Presburger arithmetic with bounded quantifier alternation

Cited in

(8)

• A remark on middle space bounded alternating Turing machines
• Time-space tradeoffs for satisfiability
• Transfinite induction within Peano arithmetic
• Bounding lemmata for non-deterministic halting times of transfinite Turing machines
• scientific article; zbMATH DE number 4033719 (Why is no real title available?)
• Fluted formulas and the limits of decidability
• Truth definition for _0 formulas and PSPACE computations
• Computation models and function algebras

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723712)