scientific article; zbMATH DE number 4200184

zbMATH Open0727.03025MaRDI QIDQ3348901FDOQ3348901

Authors: Erich Grädel 

Publication date: 1989

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

Recommendations

• Satisfiability of formulae with one \(\forall\) is decidable in exponential time
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• scientific article; zbMATH DE number 52574
• scientific article; zbMATH DE number 4116512
• scientific article; zbMATH DE number 4029504

zbMATH Keywords

classification of the prefix vocabulary classes in P and in NPcomplexity of deciding satisfiability of formulas in full first order logic

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (8)

• Title not available (Why is that?)
• Circuit complexity and the expressive power of generalized first-order formulas
• Title not available (Why is that?)
• First-Order Formulas in Conjunctive Quantificational Form
• Satisfiability of formulae with one \(\forall\) is decidable in exponential time
• Mechanizing Mathematical Reasoning
• Parameterized complexity of some prefix-vocabulary fragments of first-order logic
• The complexity of definability by open first-order formulas

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 Q3348901)