Complexity of t-tautologies

DOI10.1016/S0168-0072(01)00048-3MaRDI QIDQ5957903zbMATH OpenFDO

Authors Matthias Baaz, Petr Hájek, Franco Montagna, Helmut Veith

Publication date 6 March 2003

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0168-0072(01)00048-3

zbMATH Keywords

fuzzy logicNP completenesstriangular norm

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Fuzzy logic; logic of vagueness (03B52) Complexity of computation (including implicit computational complexity) (03D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

The paper focuses on propositional fuzzy logics based on continuous triangular norms (t-norms). After a brief overview of some principal results in the theory of t-norms, the proof of the main theorem is provided: The set of all t-tautologies (i.e. tautologies w.r.t. arbitrary continuous t-norm) is coNP-complete. From this, it also follows that the universal first-order theory of t-algebras (i.e. algebras \(\langle[0, 1], \star, \rightarrow, 0, 1\rangle\) where \(\star\) is a continuous t-norm and \(\rightarrow\) is its residuum) is coNP-complete.

Recommendations

• Computational complexity of t-norm based propositional fuzzy logics with rational truth constants
• Arithmetical complexity of fuzzy predicate logics -- a survey
• On the predicate logics of continuous t-norm BL-algebras
• Complexity Issues in Axiomatic Extensions of Lukasiewicz Logic
• Three complexity problems in quantified fuzzy logic

Cites work

• A complete many-valued logic with product-conjunction
• scientific article; zbMATH DE number 3174816 (Why is no real title available?)
• scientific article; zbMATH DE number 922613 (Why is no real title available?)
• Interpolation in fuzzy logic
• Metamathematics of fuzzy logic
• On the structure of semi-groups on a compact manifold with boundary
• Satisfiability in many-valued sentential logic is NP-complete
• Statistical metric spaces

Cited in

(23)

• The consequence relation in the logic of commutative GBL-algebras is PSPACE-complete
• Standard algebras for fuzzy propositional calculi
• Proof search and co-NP completeness for many-valued logics
• Obituary: Franco Montagna (1948--2015)
• Complexity of some language fragments of fuzzy logics
• A classification of BL-algebras
• Linearly ordered semigroups for fuzzy set theory
• Computational complexities of axiomatic extensions of monoidal t-norm based logic
• Varieties generated by standard BL-algebras
• Computational complexity of t-norm based propositional fuzzy logics with rational truth constants
• The differential semantics of Łukasiewicz syntactic consequence
• Tyrolean Complexity Tool: Features and Usage.
• Complex fuzzy sets and complex fuzzy logic an overview of theory and applications
• On Conjectures in t-Norm Based Fuzzy Logics
• Franco Montagna's work on provability logic and many-valued logic
• A new interpretation of complex membership grade
• Distinguishing standard SBL-algebras with involutive negations by propositional formulas
• scientific article; zbMATH DE number 1500525 (Why is no real title available?)
• On the computational complexity of finding hard tautologies
• Introduction
• Interpolation in Hájek's basic logic
• Complexity issues in Basic Logic
• Fuzzy logics based on \([0,1)\)-continuous uninorms

This page was built for publication: Complexity of t-tautologies

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