A finite model-theoretical proof of a property of bounded query classes within PH

DOI10.2178/jsl/1102022213zbMath1081.03027OpenAlexW2075551673MaRDI QIDQ5311769

Leszek Aleksander Kołodziejczyk

Publication date: 29 August 2005

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.101.8704

zbMATH Keywords

polynomial-time hierarchyfinite model theorycomplexity classesdescriptive complexity theoryFM-truth definitions

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)

Related Items (2)

Arity and alternation: a proper hierarchy in higher order logics ⋮ Theories of initial segments of standard models of arithmetics and their complete extensions

Cites Work

• Unnamed Item
• Relativized logspace and generalized quantifiers over finite ordered structures

This page was built for publication: A finite model-theoretical proof of a property of bounded query classes within PH