Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Complexity of some language fragments of fuzzy logics

  • Focus
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

Computational complexity of the semigroup fragment (of the algebraic semantics) and the implicational fragment of some fuzzy logics is studied, from the perspective of the complexity of the full logic. The available results appear to confirm the key role of the implicational fragments. Some other language fragments, as well as the notion of language fragment itself, are discussed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. An extension is understood to be an axiomatic extension in the same language.

  2. It follows from that paper that the implicational fragment of product logic is contained in the implicational fragment of Łukasiewicz logic; this also follows from the fact that the standard MV-algebra is isomorphic to the cut product algebra (cf. Hájek 1998).

  3. A propositional logic can itself be regarded as a syntactic fragment of its (putative) predicate expansions.

  4. Proofs are of polynomial size in formula size; the same is true about, e.g., BCI and indeed MLL, cf. Buzskowski (2008) and Kanovich (1991).

References

  • Aglianò P, Ferreirim IMA, Montagna F (2007) Basic hoops: an algebraic study of continuous t-norms. Stud Logica 87(1):73–98

    Article  MATH  MathSciNet  Google Scholar 

  • Aglianò P, Montagna F (2003) Varieties of BL-algebras I: general properties. J Pure Appl Algebra 181(2–3):105–129

    Article  MATH  MathSciNet  Google Scholar 

  • Baaz M, Hájek P, Montagna F, Veith H (2002) Complexity of t-tautologies. Ann Pure Appl Log 113(1–3):3–11

    MATH  MathSciNet  Google Scholar 

  • Bezhanishvili N, Galatos N, Spada L (2015) Canonical formulas for k-potent commutative, integral, residuated lattices. arXiv:1509.07980

  • Běhounek L, Cintula P, Hájek P (2011) Introduction to mathematical fuzzy logic. In: Cintula P, Hájek P, Noguera C (eds) Handbook of mathematical fuzzy logic, vol 1. College Publications, London, pp 1–101

    Google Scholar 

  • Blok WJ, van Alten CJ (2002) The finite embeddability property for residuated lattices, pocrims and BCK-algebras. Algebra Universalis 48(3):253–271

    Article  MATH  MathSciNet  Google Scholar 

  • Bloniarz PA, Hunt HB III, Rosenkrantz DJ (1984) Algebraic structures with hard equivalence and minimization problems. J ACM 31:879–904

    Article  MATH  MathSciNet  Google Scholar 

  • Buzskowski W (2008) On the complexity of some substructural logics. Rep Math Log 43:5–24

    MathSciNet  Google Scholar 

  • Cignoli R, Torrens A (2003) Hájek basic fuzzy logic and Łukasiewicz infinite-valued logic. Arch Math Logic 42(4):361–370

    Article  MATH  MathSciNet  Google Scholar 

  • Cignoli R, Torrens A (2006) Free algebras in varieties of Glivenko MTL-algebras satisfying the equation \(2(x^2) = (2x)^2\). Stud Logica 83(1–3):157–181

  • Cintula P, Hájek P (2009) Complexity issues in axiomatic extensions of Łukasiewicz logic. J Log Comput 19(2):245–260

    Article  MATH  Google Scholar 

  • Cintula P, Hájek P, Horčík R (2007) Formal systems of fuzzy logic and their fragments. Ann Pure Appl Log 150(1–3):40–65

    Article  MATH  MathSciNet  Google Scholar 

  • Esteva F, Godo L, Hájek P, Montagna F (2003) Hoops and fuzzy logic. J Log Comput 13(4):532–555

    Article  MATH  MathSciNet  Google Scholar 

  • Galatos N, Jipsen P, Kowalski T, Ono H (2007) Residuated lattices: an algebraic glimpse at substructural logics, volume 151 of studies in logic and the foundations of mathematics. Elsevier, Amsterdam

    MATH  Google Scholar 

  • Gehrke M, Walker C, Walker E (2004) Varieties generated by T-norms. Soft Comput 8:264–267

    Article  MATH  Google Scholar 

  • Glivenko MV (1929) Sur quelques points de la logique de M. Brouwer. Bulletins de la classe des sciences 15:183–188

    MATH  Google Scholar 

  • Hájek P (1998) Metamathematics of fuzzy logic, volume 4 of trends in logic. Kluwer, Dordrecht

    Book  MATH  Google Scholar 

  • Haniková Z (2011) Computational complexity of propositional fuzzy logics. In: Cintula P, Hájek P, Noguera C (eds) Handbook of mathematical fuzzy logic, vol 2. College Publications, London, pp 793–851

    Google Scholar 

  • Horčík R, Terui K (2011) Disjunction property and complexity of substructural logics. Theoret Comput Sci 412(31):3992–4006

    Article  MATH  MathSciNet  Google Scholar 

  • Kanovich M (1991) The multiplicative fragment of linear logic is NP-complete. Technical Report X-91-13, Institute for Logic, Language and Information, Amsterdam

  • Kisielewicz A (1994) Varieties of commutative semigroups. Trans Am Math Soc 342(1):275–306

    Article  MATH  MathSciNet  Google Scholar 

  • Komori Y (1978) Super-Łukasiewicz implicational logics. Nagoya Math J 72:127–133

    Article  MATH  MathSciNet  Google Scholar 

  • Mayr EW, Meyer AR (1982) The complexity of the word problems for commutative semigroups and polynomial ideals. Adv Math 46:305–329

    Article  MATH  MathSciNet  Google Scholar 

  • Miura S, Nagata S (1968) Certain method for generating a series of logics. Nagoya Math J 31:125–129

    Article  MATH  MathSciNet  Google Scholar 

  • Mundici D (1987) Satisfiability in many-valued sentential logic is NP-complete. Theoret Comput Sci 52(1–2):145–153

    Article  MATH  MathSciNet  Google Scholar 

  • Nelson E (1971) The lattice of equational classes of commutative semigroups. Can J Math 23:875–895

    Article  MATH  MathSciNet  Google Scholar 

  • Ono H (2010) Logic without the contraction rule and residuated lattices. Australas J Log 8:50–81

    MATH  MathSciNet  Google Scholar 

  • Perkins P (1968) Bases for equational theories of semigroups. J Algebra 11:298–314

    Article  MATH  MathSciNet  Google Scholar 

  • Statman R (1979) Intuitionistic propositional logic is polynomial-space complete. Theoret Comput Sci 9(1):67–72

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

The author was supported by the Czech Science Foundation under the Grant Number P202/11/1632, and by the long-term strategic development financing of the Institute of Computer Science RVO:67985807.

Author information

Authors and Affiliations

  1. Institute of Computer Science, Academy of Sciences of the Czech Republic, 182 07, Prague, Czech Republic

    Zuzana Haniková

Authors
  1. Zuzana Haniková
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zuzana Haniková.

Ethics declarations

Conflict of interest

The author declares that she had no conflict of interest in writing this paper.

Additional information

Communicated by A. Di Nola, D. Mundici, C. Toffalori, A. Ursini.

Dedicated to Franco Montagna, with gratitude for his contributions to logic, his support of fellow logicians, and his seasoning of serious situations with a gentle touch of humor.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Haniková, Z. Complexity of some language fragments of fuzzy logics. Soft Comput 21, 69–77 (2017). https://doi.org/10.1007/s00500-016-2346-0

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-016-2346-0

Keywords

Search

Navigation