Lewis Dichotomies in Many-Valued Logics
Studia Logica 100 (6):1271-1290 (2012)
| 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 | |||||||||
| Keywords | Parameterized satisfiability Complexity dichotomy Many-valued logics | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,672 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesVolker Weber (2009). Branching-Time Logics Repeatedly Referring to States. Journal of Logic, Language and Information 18 (4).
Maarten Marx (2002). Computing with Cylindric Modal Logics and Arrow Logics, Lower Bounds. Studia Logica 72 (2):233-252.
Walter Sinnott-Armstrong & Amit Malhotra (2002). How to Avoid Deviance (in Logic). History and Philosophy of Logic 23 (3):215--36.
Petr Cintula (2005). Two Notions of Compactness in Gödel Logics. Studia Logica 81 (1):99 - 122.
Tsutomu Hosoi (1986). Pseudo Two-Valued Evaluation Method for Intermediate Logics. Studia Logica 45 (1):3 - 8.
O. M. Anshakov, V. K. Finn & D. P. Skvortsov (1989). On Axiomatization of Many-Valued Logics Associated with Formalization of Plausible Reasonings. Studia Logica 48 (4):423 - 447.
A. S. Karpenko (1983). Factor Semantics Forn-Valued Logics. Studia Logica 42 (2-3):179 - 185.
O. Arieli, A. Avron & A. Zamansky (2011). Ideal Paraconsistent Logics. Studia Logica 99 (1-3):31-60.
Lorenzo Peña (1992). Algunas aplicaciones filosóficas de las lógicas multivalentes. Theoria 7 (1/2/3):141-163.
Gemma Robles, Francisco Salto & José M. Méndez (forthcoming). Dual Equivalent Two-Valued Under-Determined and Over-Determined Interpretations for Łukasiewicz's 3-Valued Logic Ł3. Journal of Philosophical Logic:1-30.
Richard DeWitt (2005). On Retaining Classical Truths and Classical Deducibility in Many-Valued and Fuzzy Logics. Journal of Philosophical Logic 34 (5-6):545 - 560.
C. G. Fermüller (2008). Dialogue Games for Many-Valued Logics — an Overview. Studia Logica 90 (1):43 - 68.
Analytics
Monthly downloads |
Added to index2012-11-15Total downloads3 ( #201,837 of 549,068 )Recent downloads (6 months)1 ( #63,185 of 549,068 )How can I increase my downloads? |
My notes
Discussion
