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 条
12345