Complexity of t-tautologies

, , &
Annals of Pure and Applied Logic 113 (1-3):3-11 (2001)
  Copy   BIBTEX

Abstract

A t-tautology is a propositional formula which is a tautology in all fuzzy logics defined by continuous triangular norms. In this paper we show that the problem of recognizing t-tautologies is coNP complete, and thus decidable

Categories

Keywords

Reprint years

DOI

10.1016/s0168-0072(01)00048-3

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 100,865

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Baaz, M., HaHjek, P., Montagna, F. and Veith, H., Complexity of t-tautologies (1} 3) 3} 11 Beauquier, D. and Slissenko, A., A" rst order logic for speci" cation of timed algorithms: basic properties and a decidable class (1} 3) 13} 52. [REVIEW]L. Boasson, P. Cegielski, I. Guessarian, Y. Matiyasevich, E. Dantsin, M. Gavrilovich, E. A. Hirsch & B. Konev - 2001 - Annals of Pure and Applied Logic 113 (399):400.
Distinguishing standard SBL‐algebras with involutive negations by propositional formulas.Zuzana Haniková & Petr Savický - 2008 - Mathematical Logic Quarterly 54 (6):579-596.
A note on the notion of truth in fuzzy logic.Petr Hájek & John Shepherdson - 2001 - Annals of Pure and Applied Logic 109 (1-2):65-69.
Some (non)tautologies of łukasiewicz and product logic.Petr Hájek - 2010 - Review of Symbolic Logic 3 (2):273-278.
Bounded truth table does not reduce the one-query tautologies to a random oracle.Toshio Suzuki - 2005 - Archive for Mathematical Logic 44 (6):751-762.
Reasoning processes in propositional logic.Claes Strannegård, Simon Ulfsbäcker, David Hedqvist & Tommy Gärling - 2010 - Journal of Logic, Language and Information 19 (3):283-314.
On the proof complexity of the nisan–wigderson generator based on a hard np ∩ conp function.Jan Krajíček - 2011 - Journal of Mathematical Logic 11 (1):11-27.
The Classical Constraint on Relevance.Arnon Avron - 2014 - Logica Universalis 8 (1):1-15.
Residuated logics based on strict triangular norms with an involutive negation.Petr Cintula, Erich Peter Klement, Radko Mesiar & Mirko Navara - 2006 - Mathematical Logic Quarterly 52 (3):269-282.
Advances in the ŁΠ and logics.Petr Cintula - 2003 - Archive for Mathematical Logic 42 (5):449-468.

Analytics

Added to PP
2014-01-16

Downloads
39 (#575,001)

6 months
4 (#1,246,333)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Citations of this work

Fuzzy logic and arithmetical hierarchy III.Petr Hájek - 2001 - Studia Logica 68 (1):129-142.
Kripke-style semantics for many-valued logics.Franco Montagna & Lorenzo Sacchetti - 2003 - Mathematical Logic Quarterly 49 (6):629.
Mathematical fuzzy logics.Siegfried Gottwald - 2008 - Bulletin of Symbolic Logic 14 (2):210-239.

View all 9 citations / Add more citations

References found in this work

A complete many-valued logic with product-conjunction.Petr Hájek, Lluis Godo & Francesc Esteva - 1996 - Archive for Mathematical Logic 35 (3):191-208.
Interpolation in fuzzy logic.Matthias Baaz & Helmut Veith - 1999 - Archive for Mathematical Logic 38 (7):461-489.

Add more references