scientific article; zbMATH DE number 176527

zbMATH Open0773.03006MaRDI QIDQ4035693FDOQ4035693

Authors: Erich Grädel 

Publication date: 18 May 1993

Title of this publication is not available (Why is that?)

Recommendations

• Complexity and expressive power of second-order extended Horn logic
• The expressive power of second-order propositional modal logic
• Expressivity of second order propositional modal logic
• scientific article; zbMATH DE number 7533347
• Second-Order Equational Logic (Extended Abstract)
• scientific article; zbMATH DE number 1841812
• Second order logic and the weak exponential hierarchies
• Expressive Power of Monadic Second-Order Logic and Modal μ-Calculus
• Expressing second-order sentences in intuitionistic dependence logic
• Second-order propositional modal logic: expressiveness and completeness results

zbMATH Keywords

expressive powersuccessor relationfixed point logicpolynomial time computable queriesexistential fragmentfragment of second-order logicsecond order Horn logic

Mathematics Subject Classification ID

Database theory (68P15)

Cited In (13)

• Capturing the polynomial hierarchy by second-order revised Krom logic
• The expressive power of revised Datalog on problems with closure properties
• A second-order system for polytime reasoning based on Grädel's theorem.
• Algebraic and logical characterizations of deterministic linear time classes
• Complexity barriers as independence
• Title not available (Why is that?)
• On the complexity of single-rule datalog queries.
• Capturing complexity classes by fragments of second-order logic
• A fixed-point theorem for Horn formula equations
• Semantic restrictions over second-order logic
• Logics of finite Hankel rank
• The expressive power of second-order propositional modal logic
• Complexity and expressive power of second-order extended Horn logic

This page was built for publication:

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