Capturing complexity classes with Lindström quantifiers

DOI10.1007/3-540-58338-6_59>zbMath1496.03166>OpenAlexW1979644108>MaRDI QIDQ5096870>

Johann A. Makowsky

Publication date: 18 August 2022

Published in: Mathematical Foundations of Computer Science 1994 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-58338-6_59

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Logic with extra quantifiers and operators (03C80) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19) Abstract model theory (03C95)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Relativized alternation and space-bounded computation
• Logical hierarchies in PTIME
• Definability hierarchies of generalized quantifiers
• Comparing the Expressibility of Languages Formed Using NP-Complete Operators
• Languages that Capture Complexity Classes
• Classifying the computational complexity of problems
• Expressibility and Parallel Complexity

This page was built for publication: Capturing complexity classes with Lindström quantifiers