×

Complexity issues in Basic Logic. (English) Zbl 1093.03010

Summary: We survey complexity results concerning a family of propositional many-valued logics. In particular, we address satisfiability and tautology problems for Hájek’s Basic Logic BL and for several of its schematic extensions. We review complexity bounds obtained from functional representation results, as well as techniques for dealing with non-trivial ordinal sums of continuous t-norms.

MSC:

03B52 Fuzzy logic; logic of vagueness
03B50 Many-valued logic
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aglianò P, Montagna F (2003) Varieties of BL-algebras I: general properties. J Pure Appl Algebra 181:105–129 · Zbl 1034.06009
[2] Aguzzoli S (1998) Geometric and proof–theoretic issues in Łukasiewicz propositional logics. PhD Thesis, University of Siena, Italy
[3] Aguzzoli S, Ciabattoni A (2000) Finiteness in infinite-valued Łukasiewicz logic. J Logic Lang Inf 9:5–29 · Zbl 0951.03024
[4] Aguzzoli S, Gerla B (2002) Finite-valued reductions of infinite-valued logics. Arch Math Logic 41:361–399 · Zbl 1032.03017
[5] Aguzzoli S, Gerla B (2002) On countermodels in basic logic. Neural Netw World 12:407–420
[6] Baaz M, Hájek P, Krajíček J, švejda D (1998) Embedding logics into product logic. Studia Logica 61:35–42 · Zbl 0962.03019
[7] Baaz M, Hájek P, Montagna F, Veith H (2002) Complexity of t-tautologies. Ann Pure Appl Logic 113:3–11 · Zbl 1006.03022
[8] Burris S, Sankappanavar HP (1981) A course in universal algebra, Springer, Berlin Heidelberg New York · Zbl 0478.08001
[9] Cignoli R, D’Ottaviano IML, Mundici D (2000) Algebraic foundations of many-valued reasoning, trends in logic, vol 7. Kluwer, Dordrecht
[10] Cignoli R, Esteva F, Godo L, Torrens A (2000) Basic logic is the logic of continuous t-norms and their residua. Soft Comput 4:106–112
[11] Cintula P, Gerla B Semi-normal forms and functional representation of product fuzzy logic. Fuzzy Sets Syst (to appear) · Zbl 1047.03015
[12] Esteva F, Godo L, Hájek P, Navara M (2000) Residuated fuzzy logics with an involutive negation. Arch Math Logic 39:106–112 · Zbl 0965.03035
[13] Esteva F, Godo L, Montagna F (2003) Equational characterization of the subvarieties of BL generated by t-norm algebras, (preprint) · Zbl 1045.03048
[14] Ewald G (1996) Combinatorial convexity and algebraic geometry, graduate texts in mathematics. vol 168 Springer, Berlin Heidelberg New York · Zbl 0869.52001
[15] Gerla B (2000) A note on functions associated with Gödel formulas. Soft Comput 4:206–209 · Zbl 1002.03520
[16] Gerla B (2000) Functional representation of many-valued logics based on continuous t-norms. PhD Thesis, University of Milano, Italy
[17] Gödel K (1933) Zum intuitionistischen Aussagenkalkül, Anzeiger Akademie der Wissenschaften Wien, Math.-naturwissensch. Klasse 69, (1932), 65–66. Also in Ergebnisse eines matematischen Kolloquiums 4:40
[18] Hähnle R (1993) Automated deduction in multiple-valued logics. Oxford University Press, Oxford · Zbl 0798.03010
[19] Hähnle R (1994) Many-valued logic and mixed integer programming. Ann Math Artif Intell 12:231–264 · Zbl 0856.03011
[20] Hähnle R (1997) Proof theory of many-valued logic – linear optimization – logic design: connections and interactions. Soft Comput 1:107–119
[21] Hájek P (1998) Metamathematics of fuzzy logic. Kluwer, Dordrecht · Zbl 0937.03030
[22] Hájek P (1998) Basic fuzzy logic and BL-algebras. Soft Comput 2:124–128
[23] Haniková Z (2001) Standard algebras for fuzzy propositional calculi. Fuzzy Sets Syst 124:309–320 · Zbl 0994.03018
[24] Haniková Z (2002) A note on the complexity of propositional tautologies of individual t-algebras. Neural Netw World 12:453–460
[25] Haniková Z (2003) Mathematical and metamathematical properties of fuzzy logic. PhD Thesis, Charles University in Prague
[26] McNaughton R (1951) A theorem about infinite-valued sentential logic. J Symbolic Logic 16:1–13 · Zbl 0043.00901
[27] Montagna F (2000) The free BL-algebra on one generator. Neural Netw World 5:837–844
[28] Montagna F (2001) Free BL{\(\Delta\)} Algebras. In: Antonio Di Nola, Giangiacomo Gerla (eds) Lectures on soft computing and fuzzy logic, pp 159–171
[29] Mostert PS, Shields AL (1957) On the structure of semigroups on a compact manifold with boundary. Ann Math 65:117–143 · Zbl 0096.01203
[30] Mundici D (1987) Satisfiability in many-valued sentential logic is NP-complete. Theor Comput Sci 52:145–153 · Zbl 0639.03042
[31] Mundici D (1994) A constructive proof of McNaughton’s theorem in infinite-valued logics. J Symbolic Logic 59:596–602 · Zbl 0807.03012
[32] Novák V, Perfilieva I, Močkoř J (1999) Mathematical principles of fuzzy logic. Kluwer, Boston/Dordrecht/London · Zbl 0940.03028
[33] Rose A, Rosser JB (1958) Fragments of many-valued statement calculi. Trans Am Math Soc 87:1–53 · Zbl 0085.24303
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.