Second order logic and the weak exponential hierarchies

DOI10.1007/3-540-60246-1_113zbMath1193.68115OpenAlexW1543965609MaRDI QIDQ3569000

Georg Gottlob, Nicola Leone, Helmut Veith

Publication date: 17 June 2010

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

Full work available at URL: https://doi.org/10.1007/3-540-60246-1_113

Mathematics Subject Classification ID

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

Related Items

Languages represented by Boolean formulas, The complexity class θp2: Recent results and applications in AI and modal logic, Abduction from logic programs: Semantics and complexity, Semantics and complexity of abduction from default theories, Succinct representation, leaf languages, and projection reductions, Partially ordered connectives and monadic monotone strict NP, Expressive power and complexity of partial models for disjunctive deductive databases, Succinctness as a source of complexity in logical formalisms