.png){kind=icon}
.png){kind=icon}
Return
Tabular Intermediate Logics Comparison
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-031-99536-1_20.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Tabular intermediate logics are intermediate logics characterized by finite posets treated as Kripke frames. For a poset P, let L(P) denote the corresponding tabular intermediate logic. We investigate the complexity of the following decision problem LogContain: given two finite posets P and Q, decide whether L(P) subset of L(Q). By Jankov's and de Jongh's theorem, the problem LogContain is related to the problem SPMorph: given two finite posets P and Q, decide whether there exists a surjective p-morphism from P onto Q. Both problems belong to the complexity class NP. We present two contributions. First, we describe a construction which, starting with a graph G, gives a poset Pos(G) such that there is a surjective locally surjective homomorphism (the graph-theoretic analog of a p-morphism) from G onto H if and only if there is a surjective p-morphism from Pos(G) onto Pos(H). This allows us to translate some hardness results from graph theory and obtain that several restricted versions of the problems LogContain and SPMorph are NP-complete. Among other results, we present a 18-element poset. Q such that the problem to decide, for a given poset P, whether L(P) subset of L(Q) is NP-complete. Second, we describe a polynomial-time algorithm that decides Log-Contain and SPMorph for posets T and Q, when T is a tree.
Keywords:
Tabular intermediate logic
Logics comparison
p-morphism
Journal
L
IF:
0
Papers:
21
Citations:
0