Skip to main content
Erschienen in: Soft Computing 11/2009

01.09.2009 | Original Paper

Computational complexities of axiomatic extensions of monoidal t-norm based logic

verfasst von: Moataz Saleh El-Zekey, Wafik Boulos Lotfallah, Nehad Nashaat Morsi

Erschienen in: Soft Computing | Ausgabe 11/2009

Einloggen

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

We study the computational complexity of some axiomatic extensions of the monoidal t-norm based logic (MTL), namely NM corresponding to the logic of the so-called nilpotent minimum t-norm (due to Fodor in Fuzzy Sets Syst 69:141–156, 1995); and SMTL corresponding to left-continuous strict t-norms, introduced by Esteva (and others) (Fuzzy Sets Syst 132(1):107–112, 2002; 136(3):263–282, 2003). In particular, we show that the sets of 1-satisfiable and positively satisfiable formulae of both NM and SMTL are NP-complete, while the set of 1-tautologies of NM and the set of positive tautologies of both NM and SMTL are co-NP-complete. The set of 1-tautologies of SMTL is only shown to be co-NP-hard, and it remains open if this set is in co-NP. Also, some results on the relations between these sets are obtained. We point out that results about 1-satisfiability and 1-tautology for NM are already well-known. However, in this paper, those results are proved in different ways.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Literatur
Zurück zum Zitat Aguzzoli S, Gerla B (2006) Comparing the expressive power of some fuzzy logics based on residuated t-norms. In: Proceedings of FUZZ-IEEE 2006, Vancouver, Canada, pp 2012–2019 Aguzzoli S, Gerla B (2006) Comparing the expressive power of some fuzzy logics based on residuated t-norms. In: Proceedings of FUZZ-IEEE 2006, Vancouver, Canada, pp 2012–2019
Zurück zum Zitat Aguzzoli S, Gerla B, Haniková Z (2005) Complexity issues in basic logic. Soft Comput 9:919–934MATHCrossRef Aguzzoli S, Gerla B, Haniková Z (2005) Complexity issues in basic logic. Soft Comput 9:919–934MATHCrossRef
Zurück zum Zitat Cignoli R, Esteva F, Godo L, Torrens A (2000) Basic fuzzy logic is the logic of continuous t-norms and their residua. Soft Comput 2:106–112CrossRef Cignoli R, Esteva F, Godo L, Torrens A (2000) Basic fuzzy logic is the logic of continuous t-norms and their residua. Soft Comput 2:106–112CrossRef
Zurück zum Zitat Esteva F, Godo L (2001) Monoidal t-norm based logic: towards a logic for left-continuous t-norms. Fuzzy Sets Syst 124:271–288MATHCrossRefMathSciNet Esteva F, Godo L (2001) Monoidal t-norm based logic: towards a logic for left-continuous t-norms. Fuzzy Sets Syst 124:271–288MATHCrossRefMathSciNet
Zurück zum Zitat Esteva F, Gispert J, Godo L, Montagna F (2002) On the standard and rational completeness of some axiomatic extensions of monoidal t-norm based logic. Studia Logica 71:393–420CrossRefMathSciNet Esteva F, Gispert J, Godo L, Montagna F (2002) On the standard and rational completeness of some axiomatic extensions of monoidal t-norm based logic. Studia Logica 71:393–420CrossRefMathSciNet
Zurück zum Zitat Esteva F, Godo L, Garc’a-Cerdana A (2003) On the hierarchy of t-norm based residuated fuzzy logics. In: Orlowska E, Fitting M, (eds) Studies in fuzziness and soft computing. Physica-Verlag, Heidelberg, pp 251–272 Esteva F, Godo L, Garc’a-Cerdana A (2003) On the hierarchy of t-norm based residuated fuzzy logics. In: Orlowska E, Fitting M, (eds) Studies in fuzziness and soft computing. Physica-Verlag, Heidelberg, pp 251–272
Zurück zum Zitat Esteva F, Gispert J, Noguera C (2008a) On triangular norm based axiomatic extensions of the weak nilpotent minimum logic. Math Logic Q 54:387–409MATHCrossRefMathSciNet Esteva F, Gispert J, Noguera C (2008a) On triangular norm based axiomatic extensions of the weak nilpotent minimum logic. Math Logic Q 54:387–409MATHCrossRefMathSciNet
Zurück zum Zitat Esteva F, Godo L, Noguera C (2008b) On expansions of t norm based logics with truth constants. In: Hajek G, Klement H (eds) Fuzzy logics and related structures. Elsevier, Amsterdam (in press) Esteva F, Godo L, Noguera C (2008b) On expansions of t norm based logics with truth constants. In: Hajek G, Klement H (eds) Fuzzy logics and related structures. Elsevier, Amsterdam (in press)
Zurück zum Zitat Gispert J (2003) Axiomatic extensions of the milpotent minimum logic. Rep Math Logic 37:113–123MATH Gispert J (2003) Axiomatic extensions of the milpotent minimum logic. Rep Math Logic 37:113–123MATH
Zurück zum Zitat Gottwald S (2001) A treatise on many-valued logic. Research Studies Press, Baldock Gottwald S (2001) A treatise on many-valued logic. Research Studies Press, Baldock
Zurück zum Zitat Hájek P (1998) Metamathematics of fuzzy logic. Kluwer, DordrechtMATH Hájek P (1998) Metamathematics of fuzzy logic. Kluwer, DordrechtMATH
Zurück zum Zitat Hájek P (2002) Observations on the monoidal t-norm logic. Fuzzy Sets Syst 132(1):107–112 Hájek P (2002) Observations on the monoidal t-norm logic. Fuzzy Sets Syst 132(1):107–112
Zurück zum Zitat Hájek P (2003) Basic fuzzy logic and BL-algebras II. Soft Comput 7:179–183MATH Hájek P (2003) Basic fuzzy logic and BL-algebras II. Soft Comput 7:179–183MATH
Zurück zum Zitat Höhle U (1992) M-valued sets and sheaves over integral commutative CL-monoids. In: Rodabaugh SE, Klement EP, Höhle U (eds) Applications of category theory to fuzzy subsets. Kluwer, Dordrecht, pp 32–72 Höhle U (1992) M-valued sets and sheaves over integral commutative CL-monoids. In: Rodabaugh SE, Klement EP, Höhle U (eds) Applications of category theory to fuzzy subsets. Kluwer, Dordrecht, pp 32–72
Zurück zum Zitat Höhle U (1994) Monoidal logic. In: Kruse R, Gebhardt J, Palm R (eds) Fuzzy systems in computer Science. Vieweg, Wiesbaden, pp 233–243 Höhle U (1994) Monoidal logic. In: Kruse R, Gebhardt J, Palm R (eds) Fuzzy systems in computer Science. Vieweg, Wiesbaden, pp 233–243
Zurück zum Zitat Höhle U (1995a) Commutative, residuated \(\ell\)-monoids. In: Höhle U, Klement EP (eds) Non-classical logics and their applications to fuzzy subsets. Kluwer, Dordrecht, pp 53–106 Höhle U (1995a) Commutative, residuated \(\ell\)-monoids. In: Höhle U, Klement EP (eds) Non-classical logics and their applications to fuzzy subsets. Kluwer, Dordrecht, pp 53–106
Zurück zum Zitat Höhle U (1995b) Presheaves over GL-monoids. In: Höhle U, Klement EP (eds) Non-classical logics and their applications to fuzzy subsets. Kluwer, Dordrecht, pp 127–157 Höhle U (1995b) Presheaves over GL-monoids. In: Höhle U, Klement EP (eds) Non-classical logics and their applications to fuzzy subsets. Kluwer, Dordrecht, pp 127–157
Zurück zum Zitat Immerman N (1999) Descriptive complexity. Springer, HeidelbergMATH Immerman N (1999) Descriptive complexity. Springer, HeidelbergMATH
Zurück zum Zitat Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading
Zurück zum Zitat Pavelka J (1979) On fuzzy logic. Zeitsch. f. Math. Logik, I, II, III: 25:45–52, 119–134, 447–464. Pavelka J (1979) On fuzzy logic. Zeitsch. f. Math. Logik, I, II, III: 25:45–52, 119–134, 447–464.
Zurück zum Zitat Schweizer B, Sklar A (1983) Probabilistic metric spaces. North-Holland, AmsterdamMATH Schweizer B, Sklar A (1983) Probabilistic metric spaces. North-Holland, AmsterdamMATH
Zurück zum Zitat Vetterlein T (2007) Left-continuous t-norms as functional algebras. In: Stepnicka M, Novak V, Bodenhofer U (eds) Proceedings of the 5th EUSFLAT conference, Ostrava, Czech Republic. vol 2, pp 37–43 Vetterlein T (2007) Left-continuous t-norms as functional algebras. In: Stepnicka M, Novak V, Bodenhofer U (eds) Proceedings of the 5th EUSFLAT conference, Ostrava, Czech Republic. vol 2, pp 37–43
Zurück zum Zitat Wang SM, Wang B-S, Wang X-Y (2004) A characterization of truth-functions in the nilpotent minimum logic. Fuzzy Sets Syst 145:253–266MATHCrossRef Wang SM, Wang B-S, Wang X-Y (2004) A characterization of truth-functions in the nilpotent minimum logic. Fuzzy Sets Syst 145:253–266MATHCrossRef
Metadaten
Titel
Computational complexities of axiomatic extensions of monoidal t-norm based logic
verfasst von
Moataz Saleh El-Zekey
Wafik Boulos Lotfallah
Nehad Nashaat Morsi
Publikationsdatum
01.09.2009
Verlag
Springer-Verlag
Erschienen in
Soft Computing / Ausgabe 11/2009
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-008-0382-0

Weitere Artikel der Ausgabe 11/2009

Soft Computing 11/2009 Zur Ausgabe