Product-Free Lambek Calculus Is NP-Complete

Yury Savateev

doi:10.1007/978-3-540-92687-0_26

Product-Free Lambek Calculus Is NP-Complete

Yury Savateev

Research output: Contribution to conference › Paper › 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	380
Number of pages	394
DOIs	https://doi.org/10.1007/978-3-540-92687-0_26
Publication status	Published - 2009
Event	Logical Foundations Of Computer Science - Deerfield Beach, United States Duration: 3 Jan 2009 → 6 Jan 2009 https://lfcs.ws.gc.cuny.edu/lfcs-2009/

Conference

Conference	Logical Foundations Of Computer Science
Abbreviated title	LFCS 2009
Country/Territory	United States
City	Deerfield Beach
Period	3/01/09 → 6/01/09
Internet address	https://lfcs.ws.gc.cuny.edu/lfcs-2009/

Access to Document

10.1007/978-3-540-92687-0_26

Cite this

@conference{a689fe9115e049bcbac2143be2773a38,

title = "Product-Free Lambek Calculus Is NP-Complete",

abstract = "In this paper we prove that the derivability problems forproduct-free Lambek calculus and product-free Lambek calculus allowingempty premises are NP-complete. Also we introduce a new derivabilitycharacterization for these calculi.",

author = "Yury Savateev",

year = "2009",

doi = "10.1007/978-3-540-92687-0_26",

language = "English",

pages = "380",

note = "Logical Foundations Of Computer Science, LFCS 2009 ; Conference date: 03-01-2009 Through 06-01-2009",

url = "https://lfcs.ws.gc.cuny.edu/lfcs-2009/",

}

TY - CONF

T1 - Product-Free Lambek Calculus Is NP-Complete

AU - Savateev, Yury

PY - 2009

Y1 - 2009

N2 - In this paper we prove that the derivability problems forproduct-free Lambek calculus and product-free Lambek calculus allowingempty premises are NP-complete. Also we introduce a new derivabilitycharacterization for these calculi.

AB - In this paper we prove that the derivability problems forproduct-free Lambek calculus and product-free Lambek calculus allowingempty premises are NP-complete. Also we introduce a new derivabilitycharacterization for these calculi.

U2 - 10.1007/978-3-540-92687-0_26

DO - 10.1007/978-3-540-92687-0_26

M3 - Paper

SP - 380

T2 - Logical Foundations Of Computer Science

Y2 - 3 January 2009 through 6 January 2009

ER -

Product-Free Lambek Calculus Is NP-Complete

Abstract

Conference

Access to Document

Fingerprint

Cite this