scientific article; zbMATH DE number 3767637

MaRDI QIDQ3949037zbMATH OpenFDO

Authors Pascal Michel

Publication date 1981

zbMATH Keywords

decision proceduredeterministic Turing machinedivisibilityspace complexitytheory of natural numbersupper bound

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)

Cited in

(4)

• Complexity of logical theories involving coprimality
• On the complexity of decision using destinies in \(H\)-bounded structures
• A list of arithmetical structures complete with respect to the first-order definability
• Turing machines with linear alternation, theories of bounded concatenation and the decision problem of first order theories

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 Q3949037)