COMPLETE SECOND ORDER SPECTRA

DOI10.1002/MALQ.19840303204MaRDI QIDQ3677731zbMATH OpenOpenAlexFDO

Authors Bruno Scarpellini

Publication date 1984

Published in Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/malq.19840303204

zbMATH Keywords

alternating machinescomplete spectrasecond order predicate calculus

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Model-theoretic forcing (03C25) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• scientific article; zbMATH DE number 3873293
• The Spectra of First-Order Sentences and Computational Complexity
• Lower bound results on lengths of second-order formulas
• scientific article; zbMATH DE number 3873306
• Universal quantifiers and time complexity of random access machines

Cited in

(6)

• Lower bound results on lengths of second-order formulas
• scientific article; zbMATH DE number 3873293 (Why is no real title available?)
• scientific article; zbMATH DE number 3873306 (Why is no real title available?)
• scientific article; zbMATH DE number 4204309 (Why is no real title available?)
• Universal quantifiers and time complexity of random access machines
• scientific article; zbMATH DE number 3961589 (Why is no real title available?)

This page was built for publication: COMPLETE SECOND ORDER SPECTRA

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