.png){kind=icon}
返回
Tabular Intermediate Logics Comparison
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-031-99536-1_20.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
表格中间逻辑是中间逻辑，其特征是作为Kripke框架处理的有限偏序集。对于一个偏序集P，令L(P)表示相应的表格中间逻辑。我们研究了以下决策问题LogContain的复杂性：给定两个有限偏序集P和Q，决定L(P)是否是L(Q)的子集。根据Jankov定理和de Jongh定理，LogContain问题与SPMorph问题相关：给定两个有限偏序集P和Q，决定是否存在从P到Q上的满p-同态映射。这两个问题都属于NP复杂性类。我们提出了两项贡献。首先，我们描述了一种构造方法，从图G出发，给出一个偏序集Pos(G)，使得当且仅当存在从G到H上的满局部满同态映射（p-同态映射的图论类比）时，存在从Pos(G)到Pos(H)上的满p-同态映射。这使得我们可以从图论中转换一些难度结果，并得出LogContain和SPMorph问题的几个受限版本是NP完全的。作为其他结果之一，我们给出了一个18元素的偏序集Q，使得对于给定的偏序集P，决定L(P)是否是L(Q)的子集的问题是NP完全的。其次，我们描述了一个多项式时间算法，用于当T是树时决定树T和偏序集Q的Log-Contain和SPMorph问题。
Keyword:
Tabular intermediate logic
Logics comparison
p-morphism
期刊
L
IF:
0
论文数:
21
被引数:
0
.png){kind=icon}
查看更多内容