Tabular Intermediate Logics Comparison

Paweł Rzążewski

doi:10.1007/978-3-031-99536-1_20

Tabular Intermediate Logics Comparison

2026-01-01

0

PRE

AI

P

Paweł Rzążewski

M

Michał M. Stronkowski *

DOI：10.1007/978-3-031-99536-1_20

Original

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

Tabular Intermediate Logics Comparison

Abstract

Journal

Organization

Cited Papers