zbMATH — the first resource for mathematics

Fuzzy logic and arithmetical hierarchy. III. (English) Zbl 0988.03042
[For Parts I and II see Fuzzy Sets Syst. 73, 359-363 (1995; Zbl 0857.03011) and Stud. Log. 58, 129-141 (1997; Zbl 0869.03015), respectively.]
The author discusses the arithmetical complexity of the satisfiability, provability, and tautologicity problems for his first-order basic fuzzy logic BL\(\forall\) and the subsystems of Łukasiewicz, Gödel, and product logic. For satisfiability and tautologicity he takes into account two semantics: one provided by the class of all t-algebras over [0,1] determined by a continuous t-norm, and the other one provided by BL-chains. He proves some new complexity results and surveys the known ones. In the end he provides a complete list of all possible results.

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