CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Complexity of Many-Valued Logics

Reiner Hähnle (Institutionen för datavetenskap)
Beyond Two: Theory and Applications of Multiple-Valued Logic p. 211-234. (2002)
[Kapitel]

As is the case for other logics, a number of complexity-related questions can be posed in the context of many-valued logic. Some of these, such as the complexity of the sets of satisfiable and valid formulas in various logics, are completely standard; others only make sense in a many-valued context. In this overview I concentrate on two kinds of complexity problems related to many-valued logic: first, I discuss the complexity of the membership problem in various languages, such as the satisfiable, respectively, the valid formulas in some well-known logics. Second, I discuss the size of representations of many-valued connectives and quantifiers, because this has a direct impact on the complexity of many kinds of deduction systems. I include results on both propositional and on first-order logic.



Denna post skapades 2013-06-11.
CPL Pubid: 178239

 

Institutioner (Chalmers)

Institutionen för datavetenskap (2002-2004)

Ämnesområden

Data- och informationsvetenskap

Chalmers infrastruktur