The complexity of admissible rules of Łukasiewicz logic

DOI10.1093/LOGCOM/EXS007MaRDI QIDQ5300587zbMATH OpenOpenAlexFDO

Authors Emil Jeřábek

Publication date 27 June 2013

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.6261

zbMATH Keywords

computational complexityadmissible rulePSPACE-completeŁukasiewicz logic

Mathematics Subject Classification ID

Many-valued logic (03B50) Decidability of theories and sets of sentences (03B25) Complexity of proofs (03F20)

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.

Recommendations

• Admissible Rules of Lukasiewicz Logic
• Complexity Issues in Axiomatic Extensions of Lukasiewicz Logic
• Bases of admissible rules of Łukasiewicz logic
• Complexity of admissible rules
• Computational complexity of infinite-valued Łukasiewicz propositional logic

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)