Second order logic and the weak exponential hierarchies

DOI10.1007/3-540-60246-1_113MaRDI QIDQ3569000zbMATH OpenOpenAlexFDO

Authors Georg Gottlob, N. 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) Second- and higher-order model theory (03C85) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

Recommendations

• Capturing complexity classes by fragments of second-order logic
• The Descriptive Complexity of the Deterministic Exponential Time Hierarchy
• Complexity and expressive power of second-order extended Horn logic
• scientific article; zbMATH DE number 1018738
• Arity and alternation in second-order logic

Cited in

(15)

• Partially ordered connectives and monadic monotone strict NP
• Capturing complexity classes by fragments of second-order logic
• Succinct representation, leaf languages, and projection reductions
• Expressive power and complexity of partial models for disjunctive deductive databases
• Succinctness as a source of complexity in logical formalisms
• Abduction from logic programs: Semantics and complexity
• Semantics and complexity of abduction from default theories
• Stability of weak second-order semantics
• Languages represented by Boolean formulas
• Existential Fixed-Point Logic as a Fragment of Second-Order Logic
• scientific article; zbMATH DE number 176527 (Why is no real title available?)
• scientific article; zbMATH DE number 1018738 (Why is no real title available?)
• Complexity and expressive power of second-order extended Horn logic
• The complexity class θp2: Recent results and applications in AI and modal logic
• Power domains and second-order predicates

This page was built for publication: Second order logic and the weak exponential hierarchies

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