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

被引：6
作者：
Rybakov, Mikhail [1 ]
Shkatov, Dmitry [1 ,2 ]
机构：
[1] Tver State Univ, Dept Math, Tver 170000, Russia
[2] Univ Witwatersrand, Sch Comp Sci & Appl Math, ZA-2050 Johannesburg, South Africa
来源：
JOURNAL OF LOGIC AND COMPUTATION | 2022年 / 32卷 / 05期
基金：
俄罗斯科学基金会;
关键词：
Products of modal logics; expanding relativized products; finite-variable fragments; computational complexity; satisfiability problem; validity problem; ALGORITHMIC PROPERTIES; KRIPKE FRAMES; 1ST-ORDER; UNDECIDABILITY;
D O I：
10.1093/logcom/exab080
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 about the computational complexity of single-variable fragments of logics belonging to intervals bounded by such products. We generalize our embeddability results to expanding relativized products and to products with polymodal logics.
引用
收藏
页码：853 / 870
页数：18
相关论文
共 42 条
  • [1] Alechina Natasha, 2012, Journal of Applied Non-Classical Logic, V22, P275, DOI 10.1080/11663081.2012.705960
  • [2] Multi-dimensional modal logic as a framework for spatio-temporal reasoning
    Bennett, B
    Cohn, AG
    Wolter, F
    Zakharyaschev, M
    [J]. APPLIED INTELLIGENCE, 2002, 17 (03) : 239 - 251
  • [3] Blackburn P., 1993, Journal of Logic, Language and Information, V2, P129, DOI 10.1007/BF01050635
  • [4] Chagrov Alexander, 2003, Advances in Modal Logic, V4, P71
  • [5] Fagin R., 1995, REASONING KNOWLEDGE
  • [6] Gabbay D., 1998, LOG J IGPL, V6, P73, DOI 10.1093/jigpal/6.1.73
  • [7] UNDECIDABILITY OF MODAL AND INTERMEDIATE 1ST-ORDER LOGICS WITH 2 INDIVIDUAL VARIABLES
    GABBAY, DM
    SHEHTMAN, VB
    [J]. JOURNAL OF SYMBOLIC LOGIC, 1993, 58 (03) : 800 - 823
  • [8] Non-primitive recursive decidability of products of modal logics with expanding domains
    Gabelaia, D.
    Kurucz, A.
    Wolter, F.
    Zakharyaschev, A.
    [J]. ANNALS OF PURE AND APPLIED LOGIC, 2006, 142 (1-3) : 245 - 268
  • [9] Products of 'transitive' modal logics
    Gabelaia, D
    Kurucz, A
    Wolter, F
    Zakharyaschev, M
    [J]. JOURNAL OF SYMBOLIC LOGIC, 2005, 70 (03) : 993 - 1021
  • [10] The Complexity of Decomposing Modal and First-Order Theories
    Goeller, Stefan
    Jung, Jean-Christoph
    Lohrey, Markus
    [J]. ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2015, 16 (01)
12345