We prove that propositional intuitionistic modal logics $\textbf{FS}$ (also known as $\textbf{IK}$) and $\textbf{MIPC}$ (also known as $\textbf{IS5}$) are polynomial-time embeddable into, and hence polynomial-time equivalent to, their own one-variable fragments. It follows that the one-variable fragment of $\textbf{MIPC}$ is coNEXPTIME-complete. The method of proof applies to a wide range of intuitionistic modal logics characterizable by two-dimensional frames, among them intuitionistic analogues of such classical modal logics as $\textbf{K4}$ and $\textbf{S4}$.
机构:
Southwest Univ, Inst Log & Intelligence, Tiansheng Rd 2, Chongqing, Peoples R ChinaSouthwest Univ, Inst Log & Intelligence, Tiansheng Rd 2, Chongqing, Peoples R China
Lin, Zhe
Ma, Minghui
论文数: 0引用数: 0
h-index: 0
机构:
Sun Yat Sen Univ, Inst Log & Cognit, Xingang Xi Rd 135, Guangzhou, Guangdong, Peoples R ChinaSouthwest Univ, Inst Log & Intelligence, Tiansheng Rd 2, Chongqing, Peoples R China
机构:
Tver State Univ, Dept Math, Tver, Russia
Univ Witwatersrand, Sch Comp Sci & Appl Math, Johannesburg, South AfricaTver State Univ, Dept Math, Tver, Russia
Rybakov, Mikhail
Shkatov, Dmitry
论文数: 0引用数: 0
h-index: 0
机构:
Univ Witwatersrand, Sch Comp Sci & Appl Math, Johannesburg, South AfricaTver State Univ, Dept Math, Tver, Russia