The complexity of admissible rules of Łukasiewicz logic
From MaRDI portal
Publication:5300587
DOI10.1093/LOGCOM/EXS007zbMATH Open1279.03045arXiv1108.6261OpenAlexW2128311727MaRDI QIDQ5300587FDOQ5300587
Authors: Emil Jeřábek 
Publication date: 27 June 2013
Published in: Journal Of Logic And Computation (Search for Journal in Brave)
Abstract: We investigate the computational complexity of admissibility of inference rules in infinite-valued {L}ukasiewicz propositional logic (L). It was shown in [13] that admissibility in {L} is checkable in PSPACE. We establish that this result is optimal, i.e., admissible rules of {L} are PSPACE-complete. In contrast, derivable rules of {L} are known to be coNP-complete.
Full work available at URL: https://arxiv.org/abs/1108.6261
Recommendations
Many-valued logic (03B50) Decidability of theories and sets of sentences (03B25) Complexity of proofs (03F20)
Cited In (11)
- Computational complexity of infinite-valued Łukasiewicz propositional logic
- On the complexity of validity degrees in Łukasiewicz logic
- Complexity of admissible rules
- Lexicographic rationalizability and iterated admissibility
- Bases of admissible rules of Łukasiewicz logic
- Bases of admissible rules of proper axiomatic extensions of Łukasiewicz logic
- The complexity of 3-valued Łukasiewicz rules
- Preservation of admissible rules when combining logics
- Universal proof theory: feasible admissibility in intuitionistic modal logics
- Structural completeness in many-valued logics with rational constants
- Complexity Issues in Axiomatic Extensions of Lukasiewicz Logic
This page was built for publication: The complexity of admissible rules of Łukasiewicz logic
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5300587)
