scientific article; zbMATH DE number 2042617
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Many-valued logic (03B50) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Complexity of proofs (03F20) MV-algebras (06D35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
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].
- Sequent calculi for finite-valued Lukasiewicz logics via Boolean decompositions
- Natural dualities for varieties of MV-algebras. I
- scientific article; zbMATH DE number 1420881
- Algebraic foundations of many-valued reasoning
- MODIFICATIONS OF MV-ALGEBRAS CORRESPONDING TO STRONG ORTHOLATTICES
- scientific article; zbMATH DE number 1076962
- Many-valued logics. 1: Theoretical foundations
- scientific article; zbMATH DE number 2148624
- Many-valued logics 2. Automated reasoning and practical applications
- scientific article; zbMATH DE number 1749199
- On the complexity of entailment in propositional multivalued logics
- Proof search and co-NP completeness for many-valued logics
- Automated theorem proving by resolution in non-classical logics
- scientific article; zbMATH DE number 1269582 (Why is no real title available?)
- Generalisation of proof simulation procedures for Frege systems by M. L. Bonet and S. R. Buss
- ON LOWER BOUNDS FOR COMPLEXITY OVER INFINITE BASISES FOR FUNCTIONS OF MULTI-VALUED LOGIC
- Natural dualities for varieties of MV-algebras. I
- A first polynomial non-clausal class in many-valued logic
- First-order satisfiability in Gödel logics: an NP-complete fragment
- Complexity issues in Basic Logic
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4450446)