Izvestiya: Mathematics
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Izv. RAN. Ser. Mat.:
Year:
Volume:
Issue:
Page:
Find




Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register

Izvestiya: Mathematics, 2011, Volume 75, Issue 3, Pages 631–663
DOI: https://doi.org/10.1070/IM2011v075n03ABEH002547 (Mi im4118) 		 
This article is cited in 3 scientific papers (total in 3 papers)

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

Yu. V. Savateev

M. V. Lomonosov Moscow State University
English version PDF (389 kB) Citations (3) Russian version article
References:
PDF
HTML
DOI: https://doi.org/10.1070/IM2011v075n03ABEH002547
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.
Received: 01.06.2009
Revised: 10.11.2010
Bibliographic databases:
Document Type: Article
UDC: 510.662
MSC: 03B47, 03F20, 03F52
Language: English
Original paper language: Russian
Citation: Yu. V. Savateev, “An application of proof-nets to the study of fragments of the Lambek calculus”, Izv. Math., 75:3 (2011), 631–663
Citation in format AMSBIB
\Bibitem{Sav11}
\by Yu.~V.~Savateev
\paper An application of proof-nets to the study of fragments of the Lambek calculus
\jour Izv. Math.
\yr 2011
\vol 75
\issue 3
\pages 631--663
\mathnet{http://mi.mathnet.ru//eng/im4118}
\crossref{https://doi.org/10.1070/IM2011v075n03ABEH002547}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=2847787}
\zmath{https://zbmath.org/?q=an:1231.03022}
\adsnasa{https://adsabs.harvard.edu/cgi-bin/bib_query?2011IzMat..75..631S}
\isi{https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=Publons&SrcAuth=Publons_CEL&DestLinkType=FullRecord&DestApp=WOS_CPL&KeyUT=000292303800008}
\elib{https://elibrary.ru/item.asp?id=20358797}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-80053538980}
Linking options:
  • https://www.mathnet.ru/eng/im4118
  • https://doi.org/10.1070/IM2011v075n03ABEH002547
  • https://www.mathnet.ru/eng/im/v75/i3/p189
    • This publication is cited in the following 3 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Известия Российской академии наук. Серия математическая Izvestiya: Mathematics
    Statistics & downloads:
    Abstract page:404
    Russian version PDF:187
    English version PDF:19
    References:44
    First page:7
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024