zbMATH — the first resource for mathematics

Arithmetical complexity of fuzzy predicate logics – a survey. (English) Zbl 1093.03012
Summary: Results on arithmetical complexity of sets of tautologies and satisfiable formulas of various fuzzy logics (with respect to their standard t-norm-based semantics as well as with respect to their general BL-algebra-based semantics) are surveyed. Some new results are also obtained.

03B52 Fuzzy logic; logic of vagueness
03D15 Complexity of computation (including implicit computational complexity)
03G25 Other algebras related to logic
Full Text: DOI
[1] Aglianó P, Montagna F (2003) Varieties of BL-algebras I – general properties. J Pure Appl Algebra 181:105–129 · Zbl 1034.06009
[2] Baaz M, Ciabattoni A, Fermüller C (2001) Herbrand’s theorem for prenex Gödel logic and its consequences for theorem proving. Proceedings LPAR’2001 Lecture Notes in Computer in AI 2250, Springer, Berlin Heidelberg New York, pp 201–216 · Zbl 1275.03098
[3] Baaz M, Leitsch A, Zach R (1996) Incompleteness in an infinite-valued first order Gödel logic and of some temporal logics of programs. Proceedings CSL’95. Springer, Berlin Heidelberg New York, pp 1–15
[4] Cignoli R, Esteva F, Godo L, Torrens A (2000) Basic fuzzy logic is the logic of continuous t-norms and their residua. Soft Comput 4:106–112
[5] Cignoli R, d’Ottaviano IML, Mundici D (2000) Algebraic foundations of many-valued reasoning. Kluwer Dordrecht · Zbl 0937.06009
[6] Esteva F, Godo L (2001) Monoidal t-norm based logic: towards a logic for left-continuous t-norms. Fuzzy Sets Syst 124:271–288 · Zbl 0994.03017
[7] Esteva F, Godo L, Hájek P, Montagna F (2003) Hoops and fuzzy logic. J Logic Computat 13:531–555 · Zbl 1039.03016
[8] Esteva F, Godo L, Montagna F Axiomatization of any residuated fuzzy logic defined by a continuous t-norm (Preprint) · Zbl 1037.03023
[9] Hájek P (1998) Metamathematics of fuzzy logic. Kluwer Dordrecht · Zbl 0937.03030
[10] Hájek P (2001) Fuzzy logic and arithmetical hierarchy III. Studia Logica 68:129–142 · Zbl 0988.03042
[11] Hájek P (2004) Fuzzy logic and arithmetical hierarchy IV. In: First-order revised (Hendricks et al., ed) Logos Verlag, 107–115 · Zbl 1084.03020
[12] Haniková Z (2002) A note on the complexity of propositional logics of individual t-algebras. Neural Netw World 5:441–452
[13] Jenei S, Montagna F (2002) A proof of standard completeness for Esteva’s and Godo’s logic MTL, Studia logica 70:184–192 · Zbl 0997.03027
[14] Montagna F (2001) Three complexity problems in quantified fuzzy logic. Studia logica 68:143–152 · Zbl 0985.03014
[15] Montagna F (2005) On the predicate logics of continuous t-norm BL-algebras. Archive for Math Logic 44:97–114 · Zbl 1070.03013
[16] Montagna F (2002) Ono H Kripke semantics, undecidability and standard completeness for Esteva and Godo’s logic MTL Studia Logica 71:199–206 · Zbl 1013.03021
[17] Montagna F, Sacchetti L (2003) Kripke-style semantics for many-valued logics, Mathematical Logic Quarterly (A corrigendum to be published.) · Zbl 1035.03010
[18] Mostowski A (1957) Axiomatizability of some many valued predicate calculi. Fund Math 44:165–190 · Zbl 0099.00701
[19] Ragaz ME (1981) Arithmetische Klassifikation von Formelnmengen der unendlichwertigen Logik. ETH Zürich Thesis · Zbl 0516.03011
[20] Rogers Jr H (1967) Theory of recursive functions and effective computability. McGraw-Hill, New York · Zbl 0183.01401
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.