Oracles and quantifiers

DOI10.1007/BFB0049333MaRDI QIDQ4525286zbMATH OpenFDO

Authors Y. B. Pnueli, Johann A. Makowsky

Publication date 22 January 2001

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0049333

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• scientific article; zbMATH DE number 1272994
• A perspective on Lindström quantifiers and oracles
• Capturing relativized complexity classes with Lindström quantifiers
• scientific article; zbMATH DE number 223336
• scientific article; zbMATH DE number 515747

Cited in

(15)

• Expressing uniformity via oracles
• Directions in generalized quantifier theory
• A logic-based approach to incremental reasoning on multi-agent systems
• Capturing relativized complexity classes with Lindström quantifiers
• Logical characterizations of bounded query classes. I: Logspace oracle machines
• Generalized hex and logical characterizations of polynomial space
• Oracles and Advice as Measurements
• scientific article; zbMATH DE number 1272994 (Why is no real title available?)
• Logics with Zero-One Laws that Are Not Fragments of Bounded-Variable Infinitary Logic
• scientific article; zbMATH DE number 1163938 (Why is no real title available?)
• A perspective on Lindström quantifiers and oracles
• Capturing complexity classes with Lindström quantifiers
• Logics capturing relativized complexity classes uniformly
• My writing
• NP-completeness by first-order and quantifier-free interpretations and related topics

This page was built for publication: Oracles and quantifiers

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