Open Access
Lecture Notes in Computer Science, pages 326-340
Undecidability of the Lambek Calculus with Subexponential and Bracket Modalities
Publication type: Book Chapter
Publication date: 2017-08-15
Journal:
Lecture Notes in Computer Science
Q2
SJR: 0.606
CiteScore: 2.6
Impact factor: —
ISSN: 03029743, 16113349, 18612075, 18612083
Abstract
The Lambek calculus is a well-known logical formalism for modelling natural language syntax. The original calculus covered a substantial number of intricate natural language phenomena, but only those restricted to the context-free setting. In order to address more subtle linguistic issues, the Lambek calculus has been extended in various ways. In particular, Morrill and Valentín (2015) introduce an extension with so-called exponential and bracket modalities. Their extension is based on a non-standard contraction rule for the exponential that interacts with the bracket structure in an intricate way. The standard contraction rule is not admissible in this calculus. In this paper we prove undecidability of the derivability problem in their calculus. We also investigate restricted decidable fragments considered by Morrill and Valentín and we show that these fragments belong to the NP class.
Found
Found
Top-30
Journals
|
1
2
3
4
|
|
|
Lecture Notes in Computer Science
4 publications, 50%
|
|
|
Journal of Logic, Language and Information
2 publications, 25%
|
|
|
Mathematical Structures in Computer Science
1 publication, 12.5%
|
|
|
Studies in Computational Intelligence
1 publication, 12.5%
|
|
|
1
2
3
4
|
Publishers
|
1
2
3
4
5
6
7
|
|
|
Springer Nature
7 publications, 87.5%
|
|
|
Cambridge University Press
1 publication, 12.5%
|
|
|
1
2
3
4
5
6
7
|
- We do not take into account publications without a DOI.
- Statistics recalculated only for publications connected to researchers, organizations and labs registered on the platform.
- Statistics recalculated weekly.
Are you a researcher?
Create a profile to get free access to personal recommendations for colleagues and new articles.
Metrics
Cite this
GOST |
RIS |
BibTex
Cite this
GOST
Copy
Kanovich M. et al. Undecidability of the Lambek Calculus with Subexponential and Bracket Modalities // Lecture Notes in Computer Science. 2017. pp. 326-340.
GOST all authors (up to 50)
Copy
Kanovich M., Kuznetsov S., Scedrov A. Undecidability of the Lambek Calculus with Subexponential and Bracket Modalities // Lecture Notes in Computer Science. 2017. pp. 326-340.
Cite this
RIS
Copy
TY - GENERIC
DO - 10.1007/978-3-662-55751-8_26
UR - https://doi.org/10.1007/978-3-662-55751-8_26
TI - Undecidability of the Lambek Calculus with Subexponential and Bracket Modalities
T2 - Lecture Notes in Computer Science
AU - Kanovich, Max
AU - Kuznetsov, Stepan
AU - Scedrov, Andre
PY - 2017
DA - 2017/08/15
PB - Springer Nature
SP - 326-340
SN - 0302-9743
SN - 1611-3349
SN - 1861-2075
SN - 1861-2083
ER -
Cite this
BibTex (up to 50 authors)
Copy
@incollection{2017_Kanovich,
author = {Max Kanovich and Stepan Kuznetsov and Andre Scedrov},
title = {Undecidability of the Lambek Calculus with Subexponential and Bracket Modalities},
publisher = {Springer Nature},
year = {2017},
pages = {326--340},
month = {aug}
}
Profiles