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
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
0.9034337
0 references
0.8560726
0 references
0.8505068
0 references
0.8432528
0 references
0.83055454
0 references
0.81920105
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