An application of proof-nets to the study of fragments of the Lambek calculus

Yury Savateev

doi:10.1070/IM2011v075n03ABEH002547

An application of proof-nets to the study of fragments of the Lambek calculus

Yury Savateev

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

3 Citations (Scopus)

Abstract

We use proof-nets to study the algorithmic complexity of the derivability problem for some fragments of the Lambek calculus. We prove the NP-completeness of this problem for the unidirectional fragment and the product-free fragment, and also for versions of these fragments that admit empty antecedents.

Original language	English
Pages (from-to)	631-663
Journal	Izvestiya: Mathematics
Volume	75
Issue number	3
DOIs	https://doi.org/10.1070/IM2011v075n03ABEH002547
Publication status	Published - 2011

Keywords

Lambek calculus
Algorithmic complexity
Proof nets

Access to Document

10.1070/IM2011v075n03ABEH002547

Cite this

@article{17865b564f4344569b7e5bb6ab983158,

title = "An application of proof-nets to the study of fragments of the Lambek calculus",

abstract = "We use proof-nets to study the algorithmic complexity of the derivability problem for some fragments of the Lambek calculus. We prove the NP-completeness of this problem for the unidirectional fragment and the product-free fragment, and also for versions of these fragments that admit empty antecedents.",

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

author = "Yury Savateev",

year = "2011",

doi = "10.1070/IM2011v075n03ABEH002547",

language = "English",

volume = "75",

pages = "631--663",

journal = "Izvestiya: Mathematics",

issn = "1468-4810",

publisher = "Steklov Mathematical Institute of Russian Academy of Sciences",

number = "3",

}

TY - JOUR

T1 - An application of proof-nets to the study of fragments of the Lambek calculus

AU - Savateev, Yury

PY - 2011

Y1 - 2011

N2 - We use proof-nets to study the algorithmic complexity of the derivability problem for some fragments of the Lambek calculus. We prove the NP-completeness of this problem for the unidirectional fragment and the product-free fragment, and also for versions of these fragments that admit empty antecedents.

AB - We use proof-nets to study the algorithmic complexity of the derivability problem for some fragments of the Lambek calculus. We prove the NP-completeness of this problem for the unidirectional fragment and the product-free fragment, and also for versions of these fragments that admit empty antecedents.

KW - Lambek calculus

KW - Algorithmic complexity

KW - Proof nets

U2 - 10.1070/IM2011v075n03ABEH002547

DO - 10.1070/IM2011v075n03ABEH002547

M3 - Article

SN - 1468-4810

VL - 75

SP - 631

EP - 663

JO - Izvestiya: Mathematics

JF - Izvestiya: Mathematics

IS - 3

ER -

An application of proof-nets to the study of fragments of the Lambek calculus

Abstract

Keywords

Access to Document

Fingerprint

Cite this