Truth definitions in finite models

DOI10.2178/jsl/1080938836zbMath1068.03025OpenAlexW2161264011MaRDI QIDQ5311718

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: https://doi.org/10.2178/jsl/1080938836

zbMATH Keywords

complexity classestruth definitionsfinite modelcombined complexity of logicsprenex classes of higher-order logics

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity of computation (including implicit computational complexity) (03D15) Model theory of finite structures (03C13) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Related Items

Computing queries with higher-order logics, Arity and alternation: a proper hierarchy in higher order logics, Rules with parameters in modal logic. II., Theories of initial segments of standard models of arithmetics and their complete extensions

Cites Work

• Succinctness as a source of complexity in logical formalisms
• Normal forms for second-order logic over finite structures, and classification of NP optimization problems
• Arity and alternation in second-order logic
• Unnamed Item
• Unnamed Item
• Unnamed Item