Complexity and expressive power of second‐order extended Horn logic

DOI10.1002/malq.201110034zbMath1319.68105OpenAlexW2084906772MaRDI QIDQ4915214

Zhao, Xishun, Shiguang Feng

Publication date: 9 April 2013

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.201110034

zbMATH Keywords

finite model theorydescriptive complexityHorn logic

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) 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 (1)

Capturing the polynomial hierarchy by second-order revised Krom logic

Cites Work

• Unnamed Item
• Unnamed Item
• The expressive power of stratified logic programs
• Models and quantifier elimination for quantified Horn formulas
• Computational complexity of quantified Boolean formulas with fixed maximal deficiency
• Capturing complexity classes by fragments of second-order logic
• Complete problems for deterministic polynomial time
• The polynomial-time hierarchy
• Structure and complexity of relational queries
• Horn clause queries and generalizations
• Relational queries computable in polynomial time
• Languages that Capture Complexity Classes
• Finite Model Theory

This page was built for publication: Complexity and expressive power of second‐order extended Horn logic