Satisfiability problems for propositional calculi

DOI10.1007/BF01744287MaRDI QIDQ3864500zbMATH OpenFDO

Authors Harry R. Lewis

Publication date 1979

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01744287

zbMATH Keywords

Boolean connectivesNP-completenesspolynomial-time satisfiability problemsatisfiability for formulas

Mathematics Subject Classification ID

Classical propositional logic (03B05) Complexity of computation (including implicit computational complexity) (03D15)

Cites work

• scientific article; zbMATH DE number 3583767 (Why is no real title available?)
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The Two-Valued Iterative Systems of Mathematical Logic. (AM-5)

Cited in

(24)

• A hierarchy of propositional Horn formuls
• Complexity results for classes of quantificational formulas
• Optimal satisfiability for propositional calculi and constraint satisfaction problems.
• Lewis dichotomies in many-valued logics
• Complexity results for modal dependence logic
• On the complexity of the clone membership problem
• The connectivity of Boolean satisfiability: dichotomies for formulas and circuits
• Complexity of model checking for modal dependence logic
• Generalized satisfiability for the description logic \(\mathcal{ALC}\) (extended abstract)
• The Complexity of Satisfiability for Fragments of Hybrid Logic—Part I
• The complexity of model checking for Boolean formulas
• The Complexity of Reasoning for Fragments of Default Logic
• Generalized satisfiability for the description logic \(\mathcal{ALC}\)
• scientific article; zbMATH DE number 3770947 (Why is no real title available?)
• On the applicability of Post's lattice
• Quirky quantifiers: optimal models and complexity of computation tree logic
• The complexity of satisfiability for fragments of CTL and \(\text{CTL}^*\)
• The tractability of model-checking for LTL: the good, the bad, and the ugly fragments
• Parametrised complexity of satisfiability in temporal logic
• The weight in enumeration
• The complexity of satisfiability for fragments of hybrid logic. I.
• The complexity of circumscriptive inference in Post's lattice
• Generalized modal satisfiability
• The complexity of propositional implication

This page was built for publication: Satisfiability problems for propositional calculi

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