No label defined (Q4450446)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2042617
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 2042617

      Statements

      0 references
      15 February 2004
      0 references
      many-valued logic
      0 references
      complexity of word problem
      0 references
      satisfiability problem
      0 references
      survey
      0 references
      free MV-algebras
      0 references
      This is a survey on complexity-theoretic issues about many-valued logic and its proof theory. After several decades of relative quiescence, research in many-valued logic has been rapidly expanding in the last twenty years, because of its applications to computer science (circuit verification, logic-based control, error-correcting codes with feedback, logic programming) and also because some algebras of many-valued logics, notably MV-algebras, have an interesting mathematical theory. For background see \textit{P. Hajek}'s book [Metamathematics of fuzzy logic. Kluwer Academic Publishers, Dordrecht (1998; Zbl 0937.03030)]. While the complexity of the propositional fragment of certain many-valued logics is often the same as for Boolean logic, this is no longer so for their first-order extensions. The author mainly concentrates on the complexity of satisfiability and tautology problems. McNaughton's representation of free MV-algebras is discussed in a special subsection. See \textit{R. L. O. Cignoli}, \textit{I. M. L. D'Ottaviano} and \textit{D. Mundici}, Algebraic foundations of many-valued reasoning. Kluwer Academic Publishers, Dordrecht (2000; Zbl 0937.06009) for more information on Łukasiewicz many-valued calculus and MV-algebras. Two main proof techniques are presented: reduction to mixed integer programming and reduction to classical logic. In the final sections the author discusses the size of representations of many-valued connectives and quantifiers. A list of 70 background references is provided. For the entire collection see [Zbl 1015.00007].
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references