Lower bound results on lengths of second-order formulas

DOI10.1016/0168-0072(85)90034-XzbMath0586.03029MaRDI QIDQ1071760

Bruno Scarpellini

Publication date: 1985

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

complexity theorysecond order spectrumalternating machineslength of formulassecond order predicate calculussecond order quantifier

Mathematics Subject Classification ID

Related Items (2)

Universal quantifiers and time complexity of random access machines ⋮ Complex Boolean networks obtained by diagonalization

Cites Work

• Handbook of mathematical logic. With the cooperation of H. J. Keisler, K. Kunen, Y. N. Moschovakis, A. S. Troelstra. 2nd printing
• The polynomial-time hierarchy
• Complexity of Subcases of Presburger Arithmetic
• Complexity classes and theories of finite models
• Turing machines and the spectra of first-order formulas
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bound results on lengths of second-order formulas