Proof search and co-NP completeness for many-valued logics
type: Item
instance of: scholarly article
title: Proof search and co-NP completeness for many-valued logics
zbMATH Open document ID: 1390.03023
author: Mattia Bongini
author: Agata Ciabattoni
author: Franco Montagna
published in: Fuzzy Sets and Systems
publication date: 2018-02-19T00:00:00Z
review text: This paper generalizes relational hypersequents (as introduced in [the second author et al., Lect. Notes Comput. Sci. 3452, 496--510 (2005; Zbl 1109.03019)]) to disjunctions of arbitrary semantic predicates over multisets of formules. The authors introduce a methodology to define relational hypersequent calculi for a large class of many-valued logics and identify sufficient conditions on these calculi that guarantee the co-NP completeness of the logics. The methodology applies to projective and semi-projective logics as well as to Łukasiewicz logic, product logic and Hájek's basic fuzzy logic BL. It provides a unified perspective on most of the known complexity results for many valued logics. As the authors claim, this article subsumes all existing results on sequents of relations and relational hypersequent calculi found in [\textit{M. Baaz} and \textit{C. G. Fermüller}, Lect. Notes Comput. Sci. 1617, 36--50 (1999; Zbl 0931.03066); \textit{M. Baaz} et al., in: Beyond two: Theory and applications of multiple-valued logic. Heidelberg: Physica-Verlag. 157--180 (2003; Zbl 1041.03020); the second and the third author, Theor. Comput. Sci. 480, 26--42 (2013; Zbl 1322.03019); the second author et al., loc. cit.; \textit{T. Vetterlein}, J. Log. Comput. 18, No. 1, 35--57 (2008; Zbl 1139.03018); \textit{S. Bova} and the third author, ACM Trans. Comput. Log. 9, No. 3, Article No. 21, 26 p. (2008; Zbl 1367.03024)].
reviewed by: Albert Hoogewijs
Mathematics Subject Classification ID: 03B50
Mathematics Subject Classification ID: 03F03
Mathematics Subject Classification ID: 03B25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6840670
zbMATH Keywords: many-valued logics
zbMATH Keywords: co-NP completeness
zbMATH Keywords: relational hypersequents
describes a project that uses: MUltlog
MaRDI profile type: Publication
full work available at URL: j.fss.2015.02.016
OpenAlex ID: W2119157651
cites work: The pure calculus of entailment
cites work: Q3837723
cites work: A constructive analysis of RM
cites work: Decomposition proof systems for Gödel-Dummett logics
cites work: Q4450443
cites work: Q4263005
cites work: Automated deduction for many-valued logics
cites work: MUltlog 1.0: Towards an expert system for many-valued logics
cites work: Complexity of t-tautologies
cites work: Finite-valued semantics for canonical labelled calculi
cites work: Display logic
cites work: \(n\)-contractive BL-logics
cites work: Algebraizable logics
cites work: Proof search in Hájek's basic logic
cites work: Q3934450
cites work: Logic for Programming, Artificial Intelligence, and Reasoning
cites work: Proof theory for locally finite many-valued logics: semi-projective logics
cites work: Monoidal t-norm based logic: Towards a logic for left-continuous t-norms
cites work: Untersuchungen über das logische Schliessen. I
cites work: Metamathematics of fuzzy logic
cites work: Disjunction property and complexity of substructural logics
cites work: On Computational Complexity of Semilinear Varieties
cites work: Sequent and hypersequent calculi for abelian and łukasiewicz logics
cites work: Analytic calculi for product logics
cites work: Analytic Calculi for Logics of Ordinal Multiples of Standard t-Norms
cites work: Q3813613
DOI: 10.1016/J.FSS.2015.02.016
Recommended article: Q3105088
Recommended article: Q4450446
Recommended article: Q3754598
Recommended article: Q3726086
Recommended article: Resolution-based theorem proving for many-valued logics
Recommended article: Q4534923
Recommended article: Many-valued computational logics
Recommended article: Q3786468
Recommended article: Satisfiability in many-valued sentential logic is NP-complete
Recommended article: On the complexity of entailment in propositional multivalued logics
description: scientific article; zbMATH DE number 6840670