The monotone Lambek calculus is NP-complete

被引：0

作者：

Pentus, Mati ^{[1
]}

机构：

[1] Moscow State University, Moscow

来源：

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | 2014年 / 8222卷

基金：

俄罗斯基础研究基金会;

关键词：

Complexity; Lambek calculus; Structural rule;

D O I：

10.1007/978-3-642-54789-8_20

中图分类号：

学科分类号：

摘要：

We consider the Lambek calculus with the additional structural rule of monotonicity (weakening). We show that the derivability problem for this calculus is NP-complete (both for the full calculus and for the product-free fragment). The same holds for the variant that allows empty antecedents. To prove NP-hardness of the product-free fragment, we provide a mapping reduction from the classical satisfiability problem SAT. This reduction is similar to the one used by Yury Savateev in 2008 to prove NP-hardness (and hence NP-completeness) of the product-free Lambek calculus. © Springer-Verlag Berlin Heidelberg 2014.

引用

页码：368 / 380

页数：12

共 50 条

[31] Extending the Lambek Calculus with Classical Negation
Michael Kaminski
Studia Logica, 2022, 110 : 295 - 317
[32] The Lambek Calculus with Iteration: Two Variants
Kuznetsov, Stepan
LOGIC, LANGUAGE, INFORMATION, AND COMPUTATION: 24TH INTERNATIONAL WORKSHOP, WOLLIC 2017, LONDON, UK, JULY 18-21, 2017, PROCEEDINGS, 2017, 10388 : 182 - 198
[33] Lambek vs. Lambek: Functorial vector space semantics and string diagrams for Lambek calculus
Coecke, Bob
Grefenstette, Edward
Sadrzadeh, Mehrnoosh
ANNALS OF PURE AND APPLIED LOGIC, 2013, 164 (11) : 1079 - 1100
[34] LINEARLY-GROWING REDUCTIONS OF KARP'S 21 NP-COMPLETE PROBLEMS
Filar, Jerzy A.
Haythorpe, Michael
Taylor, Richard
NUMERICAL ALGEBRA CONTROL AND OPTIMIZATION, 2018, 8 (01): : 1 - 16
[35] A BRIEF SURVEY OF FRAMES FOR THE LAMBEK CALCULUS
DOSEN, K
ZEITSCHRIFT FUR MATHEMATISCHE LOGIK UND GRUNDLAGEN DER MATHEMATIK, 1992, 38 (02): : 179 - 187
[36] Extending the Lambek Calculus with Classical Negation
Kaminski, Michael
STUDIA LOGICA, 2022, 110 (02) : 295 - 317
[37] Full Lambek Calculus in natural deduction
Zimmermann, Ernst
MATHEMATICAL LOGIC QUARTERLY, 2010, 56 (01) : 85 - 88
[38] Versions of a Local Contraction Subexponential in the Lambek Calculus
Valinkin, M. V.
ALGEBRA AND LOGIC, 2022, 61 (04) : 271 - 287
[39] The Sturm-Liouville Eigenvalue Problem and NP-Complete Problems in the Quantum Setting with Queries
A. Papageorgiou
H. Woźniakowski
Quantum Information Processing, 2007, 6 : 101 - 120
[40] The sturm-liouville eigenvalue problem and NP-complete problems in the quantum setting with queries
Papageorgiou, A.
Wozniakowski, H.
QUANTUM INFORMATION PROCESSING, 2007, 6 (02) : 101 - 120

← 1 2 3 4 5 →