Product-free Lambek calculus is NP-complete

Yury Savateev

doi:10.1016/j.apal.2011.09.017

Product-free Lambek calculus is NP-complete

Yury Savateev

Research output: Contribution to journal › Article › peer-review

Abstract

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.

Original language	English
Pages (from-to)	775-788
Journal	Annals of Pure and Applied Logic
Volume	163
Issue number	7
DOIs	https://doi.org/10.1016/j.apal.2011.09.017
Publication status	Published - Jul 2012

Keywords

Lambek calculus
Algorithmic complexity
Proof nets

Access to Document

10.1016/j.apal.2011.09.017

Cite this

@article{d300d13e800e4de3b6fd3e82191e9101,

title = "Product-free Lambek calculus is NP-complete",

abstract = "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.",

keywords = "Lambek calculus, Algorithmic complexity, Proof nets",

author = "Yury Savateev",

year = "2012",

month = jul,

doi = "10.1016/j.apal.2011.09.017",

language = "English",

volume = "163",

pages = "775--788",

journal = "Annals of Pure and Applied Logic",

issn = "0168-0072",

publisher = "Elsevier",

number = "7",

}

TY - JOUR

T1 - Product-free Lambek calculus is NP-complete

AU - Savateev, Yury

PY - 2012/7

Y1 - 2012/7

N2 - 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.

AB - 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.

KW - Lambek calculus

KW - Algorithmic complexity

KW - Proof nets

U2 - 10.1016/j.apal.2011.09.017

DO - 10.1016/j.apal.2011.09.017

M3 - Article

SN - 0168-0072

VL - 163

SP - 775

EP - 788

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 7

ER -

Product-free Lambek calculus is NP-complete

Abstract

Keywords

Access to Document

Fingerprint

Cite this