Logical characterizations of PSPACE

DOI10.1007/978-3-540-30124-0_29MaRDI QIDQ5311269zbMATH OpenOpenAlexFDO

Authors David Richerby

Publication date 22 August 2005

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

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

zbMATH Keywords

choice operatorsdescriptive complexityFinite model theorypartial fixed points

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Logical and schematic characterization of complexity classes
• Generalized hex and logical characterizations of polynomial space
• scientific article; zbMATH DE number 1540059
• Complete problems for fixed-point logics
• Infinitary logic and inductive definability over finite structures

Cited in

(8)

• Logical and schematic characterization of complexity classes
• A logical account of pspace
• scientific article; zbMATH DE number 5722524 (Why is no real title available?)
• On complete problems, relativizations and logics for complexity classes
• Expressivity within second-order transitive-closure logic
• Descriptive complexity for neural networks via Boolean networks
• Logical characterizations of weighted complexity classes
• Descriptive complexity and weighted Turing machines

This page was built for publication: Logical characterizations of PSPACE

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