The complexity of admissible rules of Łukasiewicz logic

0392459 - MÚ 2014 RIV GB eng J - Journal Article
Jeřábek, Emil
The complexity of admissible rules of Łukasiewicz logic.
Journal of Logic and Computation. Roč. 23, č. 3 (2013), s. 693-705. ISSN 0955-792X. E-ISSN 1465-363X
R&D Projects: GA AV ČR IAA100190902; GA AV ČR IAA900090703; GA MŠMT(CZ) 1M0545
Institutional support: RVO:67985840
Keywords : Łukasiewicz logic * admissible rule * bases of admissible rules
Subject RIV: BA - General Mathematics
Impact factor: 0.504, year: 2013
http://logcom.oxfordjournals.org/content/23/3/693

We investigate the computational complexity of admissibility of inference rules in infinite-valued Łukasiewicz propositional logic (Ł). It was shown in [13] that admissibility in Ł is checkable in PSPACE. We establish that this result is optimal, i.e. admissible rules of Ł are PSPACE-complete. In contrast, derivable rules of Ł are known to be coNP-complete.
Permanent Link: http://hdl.handle.net/11104/0221328