Lewis Dichotomies in Many-Valued Logics

Studia Logica 100 (6):1271-1290 (2012)
  Copy   BIBTEX

Abstract

In 1979, H. Lewis shows that the computational complexity of the Boolean satisfiability problem dichotomizes, depending on the Boolean operations available to formulate instances: intractable (NP-complete) if negation of implication is definable, and tractable (in P) otherwise [21]. Recently, an investigation in the same spirit has been extended to nonclassical propositional logics, modal logics in particular [2, 3]. In this note, we pursue this line in the realm of many-valued propositional logics, and obtain complexity classifications for the parameterized satisfiability problem of two pertinent samples, Kleene and Gödel logics

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Analytics

Added to PP
2012-11-15

Downloads
92 (#171,146)

6 months
4 (#319,344)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

The two-valued iterative systems of mathematical logic.Emil Leon Post - 1941 - London,: H. Milford, Oxford university press.
Free l-algebras.Alfred Horn - 1969 - Journal of Symbolic Logic 34 (3):475-480.
The Two-valued Iterative Systems of Mathematical Logic.H. E. Vaughan - 1941 - Journal of Symbolic Logic 6 (3):114-115.

Add more references