Geodesic
An application of proof-nets to the study of fragments of the Lambek calculus
Izvestiya. Mathematics , Tome 75 (2011) no. 3, pp. 631-663

Voir la notice de l'article provenant de la source Math-Net.Ru

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: algorithmic complexity, proof-nets.
Mots-clés : Lambek calculus 
@article{IM2_2011_75_3_a7,
     author = {Yu. V. Savateev},
     title = {An application of proof-nets to the study of fragments of the {Lambek} calculus},
     journal = {Izvestiya. Mathematics },
     pages = {631--663},
     publisher = {mathdoc},
     volume = {75},
     number = {3},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/IM2_2011_75_3_a7/}
}
TY  - JOUR
AU  - Yu. V. Savateev
TI  - An application of proof-nets to the study of fragments of the Lambek calculus
JO  - Izvestiya. Mathematics 
PY  - 2011
SP  - 631
EP  - 663
VL  - 75
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IM2_2011_75_3_a7/
LA  - en
ID  - IM2_2011_75_3_a7
ER  - 
%0 Journal Article
%A Yu. V. Savateev
%T An application of proof-nets to the study of fragments of the Lambek calculus
%J Izvestiya. Mathematics 
%D 2011
%P 631-663
%V 75
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IM2_2011_75_3_a7/
%G en
%F IM2_2011_75_3_a7
Yu. V. Savateev. An application of proof-nets to the study of fragments of the Lambek calculus. Izvestiya. Mathematics , Tome 75 (2011) no. 3, pp. 631-663. http://geodesic.mathdoc.fr/item/IM2_2011_75_3_a7/