Complexity of finite-variable fragments of products with non-transitive modal logics

MIKHAIL RYBAKOV; DMITRY SHKATOV

首页> 外文期刊>Journal of logic and computation >Complexity of finite-variable fragments of products with non-transitive modal logics

【24h】

Complexity of finite-variable fragments of products with non-transitive modal logics

机译：Complexity of finite-variable fragments of products with non-transitive modal logics

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

We show that products of propositional modal logics where at least one factor is one of the monomodal logics K, KT,KB and KTB are polynomial-time embeddable into their single-variable fragments. Consequently, we obtain results aboutthe computational complexity of single-variable fragments of logics belonging to intervals bounded by such products. Wegeneralize our embeddability results to expanding relativized products and to products with polymodal logics.

著录项

来源
《Journal of logic and computation》 |2022年第5期|853-870|共18页
作者
MIKHAIL RYBAKOV; DMITRY SHKATOV;
展开▼
作者单位

Department of Mathematics, Tver State University, Tver170000, Russia;

School of Computer Science and Applied Mathematics,University of the Witwatersrand, Johannesburg, WITS2050, South Africa andDepartment of Mathematics, Tver State University, Tver 170000, Russia;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类
关键词
Products of modal logics; expanding relativized products; finite-variable fragments; computational complexity; satisfiability problem; validity problem;

Complexity of finite-variable fragments of products with non-transitive modal logics

摘要

著录项

相关主题

期刊订阅