Decidability of Modal Logics of Non-k-Colorable Graphs

被引：0

作者：

Shapirovsky, Ilya ^{[1
]}

机构：

[1] New Mexico State Univ, Las Cruces, NM 88003 USA

来源：

LOGIC, LANGUAGE, INFORMATION, AND COMPUTATION, WOLLIC 2023 | 2023年 / 13923卷

关键词：

chromatic number; modal logic; difference modality; decidability; finite model property; filtration;

D O I：

10.1007/978-3-031-39784-4_22

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We consider the bimodal language, where the first modality is interpreted by a binary relation in the standard way, and the second is interpreted by the relation of inequality. It follows from Hughes (1990), that in this language, non-k-colorability of a graph is expressible for every finite k. We show that modal logics of classes of non-k-colorable graphs (directed or non-directed), and some of their extensions, are decidable.

引用

页码：351 / 361

页数：11

共 15 条

[1] Blackburn P., 2001, CAMBRIDGE TRACTS THE, V53
[2] CHAGROV A., 1997, MODAL LOGIC, V35
[3] de Grey ADNJ, 2018, Arxiv, DOI arXiv:1804.02385
[4] THE MODAL LOGIC OF INEQUALITY
DERIJKE, M
[J]. JOURNAL OF SYMBOLIC LOGIC, 1992, 57 (02) : 566 - 584
[5] Someone knows that local reasoning on hypergraphs is a weakly aggregative modal logic
Ding, Yifeng
Liu, Jixin
Wang, Yanjing
[J]. SYNTHESE, 2023, 201 (02)
[6] The Chromatic Number of the Plane is At Least 5: A New Proof
Exoo, Geoffrey
Ismailescu, Dan
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2020, 64 (01) : 216 - 226
[7] Fine K., 1975, Studies in Logic and the Foundations of Mathematics, V82, P15, DOI DOI 10.1016/S0049-237X(08)70723-7
[8] MODAL LOGIC WITH NAMES
GARGOV, G
GORANKO, V
[J]. JOURNAL OF PHILOSOPHICAL LOGIC, 1993, 22 (06) : 607 - 636
[9] Erdos graphs resolve Fine's canonicity problem
Goldblatt, R
Hodkinson, I
Venema, Y
[J]. BULLETIN OF SYMBOLIC LOGIC, 2004, 10 (02) : 186 - 208
[10] The Finite Model Property for Logics with the Tangle Modality
Goldblatt, Robert
Hodkinson, Ian
[J]. STUDIA LOGICA, 2018, 106 (01) : 131 - 166

← 1 2 →