逻辑学学术速递[1.10]
Update！H5支持摘要折叠，体验更佳！点击阅读原文访问arxivdaily.com，涵盖CS|物理|数学|经济|统计|金融|生物|电气领域，更有搜索、收藏等功能！
cs.LO逻辑学，共计2篇
【1】 Decision problem of some bundled FOML fragments
标题：若干捆绑FOML片段的判定问题
链接：https://arxiv.org/abs/2201.02336
摘要：Over increasing domain interpretations, \exists\Box and \forall\Box bundled
fragments are decidable and over constant domain interpretations, \exists\Box
bundled fragment is decidable while \forall\Box bundled fragment is
undecidable. Based on the existing results,we show that over increasing domain
interpretations, \Box\exists and \Box\forall bundled fragments are decidable as
well. On the other hand, over constant domain interpretations, \Box\forall
bundled fragment is undecidable and \Box\exists^2 bundled fragment, an
extension of \Box\exists bundled fragment, is undecidable neither.
【2】 TOWER-Complete Problems in Contraction-Free Substructural Logics
标题：无收缩子结构逻辑中的塔式完备性问题
链接：https://arxiv.org/abs/2201.02496
备注：Draft
摘要：We investigate the computational complexity of a family of substructural
logics with exchange and weakening but without contraction. With the aid of the
techniques provided by Lazi\'c and Schmitz (2015), we show that the
deducibility problem for full Lambek calculus with exchange and weakening
($\mathbf{FL}_{\mathbf{ew}}$) is TOWER-complete, where TOWER is one of the
non-elementary complexity classes introduced by Schmitz (2016). The same
complexity result holds even for deducibility in BCK-logic, i.e., the
implicational fragment of $\mathbf{FL}_{\mathbf{ew}}$. We furthermore show the
TOWER-completeness of the provability problem for elementary affine logic,
which was proved to be decidable by Dal Lago and Martini (2004).
机器翻译，仅供参考
点击“阅读原文”获取带摘要的学术速递