• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Product-Free Lambek Calculus Is NP-Complete

Annals of Pure and Applied Logic. 2012. Vol. 163. P. 775-788.
Savateev Y.

In this paper we prove that the derivability problems for product-free Lambek calculus and product-free Lambek calculus allowing empty premises are NP-complete. Also we introduce a new derivability characterization for these calculi.