Logics capturing relativized complexity classes uniformly

DOI10.1007/3-540-60178-3_98MaRDI QIDQ6064295zbMATH OpenOpenAlexFDO

Authors Johann A. Makowsky, Y. B. Pnueli

Publication date 12 December 2023

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

Full work available at URL https://doi.org/10.1007/3-540-60178-3_98

zbMATH Keywords

logarithmic spacecomplexity classorder logicmodel checkergeneralize quantifier

Mathematics Subject Classification ID

Mathematical logic and foundations (03-XX)

Recommendations

• On complete problems, relativizations and logics for complexity classes
• Capturing relativized complexity classes with Lindström quantifiers
• Logics for complexity classes
• Logics which capture complexity classes over the reals
• Logics which capture complexity classes over the reals
• scientific article; zbMATH DE number 3885883
• Capturing complexity classes with Lindström quantifiers
• scientific article; zbMATH DE number 4106269
• scientific article; zbMATH DE number 4011940
• Approximate formulae for a logic that capture classes of computational complexity

Cites work

• scientific article; zbMATH DE number 3941493 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1555186 (Why is no real title available?)
• scientific article; zbMATH DE number 1555193 (Why is no real title available?)
• scientific article; zbMATH DE number 3995053 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• Expressibility and Parallel Complexity
• Fixed-point extensions of first-order logic
• Generalized Quantifiers and Logical Reducibilities
• Inductive definitions over finite structures
• Languages that Capture Complexity Classes
• Nondeterministic Space is Closed under Complementation
• Parallel computation and the NC hierarchy relativized
• Relativization of questions about log space computability
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• Relativized alternation and space-bounded computation
• Relativized logspace and generalized quantifiers over finite ordered structures
• Space-bounded hierarchies and probabilistic computations

Cited in

(7)

• Applicative theories for logarithmic complexity classes
• My writing
• Linear algebraic quantifiers
• Logics for complexity classes
• Capturing Relativized Complexity Classes without Order
• Logics of finite Hankel rank
• Logics which capture complexity classes over the reals

This page was built for publication: Logics capturing relativized complexity classes uniformly

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