The complexity of admissible rules of Łukasiewicz logic

Abstract

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.

14 pages, 2 figures; to appear in Journal of Logic and Computation

References in corpus (1)

• Rational polyhedra and projective lattice-ordered abelian groups with order unit

Cited by in corpus (3)

• Exact Unification and Admissibility
• Preservation of admissible rules when combining logics
• Structural completeness in many-valued logics with rational constants