Number of the records: 1
The complexity of admissible rules of Łukasiewicz logic
- 1.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
File Download Size Commentary Version Access Jerabek1.pdf 1 226.3 KB Publisher’s postprint require
Number of the records: 1